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 chckString(string1,string2):
    length = len(string1)
    i = 0
    j = 0
    interaction = 0
    while(i<length):
        if(not(string1[i]==string2[j])):
            i = i+1
            if(interaction==1):
                return 0
            interaction = interaction + 1
            continue
        i = i+1
        j = j+1
    return 1
 
def chckDoubleString(string):
    length = len(string)
    mid    = length/2
    
    if (length==1):
    	return 0
    if(length%2==0):
    	if(length==0):
    		return 0
    	else:
	        for i in range(mid):
	            if(not(string[i]==string[mid+i])):
	                return 0
	        return 1
    else:
        str1 = string[:mid+1]
        str2 = string[mid+1:]
        flag = chckString(str1,str2+" ")
        if(flag==0):
            str1 = string[mid:]
            str2 = string[:mid]
            flag = chckString(str1,str2+" ")
        return flag
 
for tests in range(input()):
    S = raw_input()
    
    if(chckDoubleString(S)==1):
        print "YES"
    else:
        print "NO"