One day, Chef prepared D brand new dishes. He named the i-th dish by a string Si. After the cooking, he decided to categorize each of these D dishes as special or not.


A dish Si is called special if it's name (i.e. the string Si) can be represented in the form of a double string by removing at most one (possibly zero) character from it's name from any position.


A string is called a double string if it can be represented as a concatenation of two identical, non-empty strings.
e.g. "abab" is a double string as it can be represented as "ab" + "ab" where + operation denotes concatenation.
Similarly, "aa", "abcabc" are double strings whereas "a", "abba", "abc" are not.


Input

First line of the input contains an integer D denoting the number of dishes prepared by Chef on that day.
Each of the next D lines will contain description of a dish.

The i-th line contains the name of i-th dish Si.
 	


Output
For each of the D dishes, print a single line containing "YES" or "NO" (without quotes) denoting whether the dish can be called as a special or not.

Constraints

1 ≤ D ≤ 10^6
1 ≤ |Si| ≤ 10^6.
Each character of string Si will be lower case English alphabet (i.e. from 'a' to 'z').


Example
Input:
3
aba
abac
abcd

Output:
YES
NO
NO



Explanation
Example case 1.
We can remove the character at position 1 (0-based index) to get "aa" which is a double string. Hence, it is a special dish.
Example case 2.
It is not possible to remove the character at any of the position to get the double string. Hence, it is not a special dish.
def is_subseq(x, y):
    i = 0
    for c in x:
        while i < len(y) and y[i] != c: i += 1
        if i == len(y): return False
        i += 1
    return True

for cas in xrange(input()):
    a = raw_input()
    n = len(a)
    print 'YES' if n > 1 and (is_subseq(a[:n/2], a[n/2:]) or is_subseq(a[(n+1)/2:], a[:(n+1)/2])) else 'NO'