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.
for case in xrange(input()):
	input_arr = raw_input().strip().split()
	for each in input_arr:
		l = len(each)
		if l < 2:
			print "NO"
		else :				
			temp1 = each[:l/2] #short if length is odd
			temp2 = each[l/2:]
			if l % 2 == 0:
				if temp2 == temp1:
					print "YES"
				else:
					print "NO"
			else:
				# 1st part
				temp1 = each[:l/2] #short if length is odd
				temp2 = each[l/2:]
				# print temp1
				# print temp2
				j = l/2
				# print "l/2 : "+str(j)
				count = 0
				i=0
				while  i < l/2:
					if count== 2:
						# print "NO"
						break
					# print "i : %s ,j : %s  " % (i,j)
					if each[i]!=each[j]:
						count+=1
						i-=1				
					i+=1
					j+=1

				# 2nd part
				temp1 = each[:l/2+1] 
				temp2 = each[l/2+1:] #short if length is odd
				j = l/2+1
				i = 0
				# print temp1
				# print temp2
				# print "l/2 : "+str(j)
				count1 = 0
				while j < l :
					if count1== 2:
						# print "NO"
						break
					# print "i : %s ,j : %s  " % (i,j)
					if each[i]!=each[j]:
						count1+=1
						j-=1				
					i+=1
					j+=1

				if count == 2 and count1 == 2:
					print "NO"
				else:
					print "YES"