PALDR - Even Palindrome

Palindrome is a string that has the property of reading the same in either direction (left to right or right to left). You are to determine whether a given string can be expressed as a concatenation of palindromes of even length.

Note: A string can be formed by concatenation of any number of even palindrome strings.

Input

First line contains T (T < 100), the number of test cases. T lines follow, each containing the string corresponding to that particular test case.

Note:

There might be a new-line character (i.e. '\r' in C++) at the end of each line. Be careful with your languages.

Output

Output consists of T lines, one corresponding to each test case. You should output YES if the string can be expressed as concatination of even length palindromes and NO otherwise.

Example

Input:
3
madam
aA
aabb

Output:
NO
NO
YES 

Constraints

Length of string ≤ 106


Added by:Race with time
Date:2009-02-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Code Craft 09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.