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 isSubseq(a, b):
	j = 0
	for c in a:
		while j < len(b) and b[j] != c:
			j += 1
		if j == len(b):
			return False
		j += 1
	return True

def test(s):
	if len(s) <= 1:
		return "NO"
	n = len(s)
	if isSubseq(s[: n / 2], s[n / 2: ]) or \
		isSubseq(s[(n + 1) / 2 : ], s[: (n + 1 ) / 2]):
		return "YES"
	return "NO"



d = int(raw_input())
for i in xrange(d):
	print test(raw_input())