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 ≤ 106
- 1 ≤ |Si| ≤ 106.
- Each character of string Si will be lower case English alphabet (i.e. from 'a' to 'z').
-----Subtasks-----
Subtask #1 : (20 points)
- Sum of |Si| in an input file doesn't exceed 2 * 103
Subtask 2 : (80 points) 
- Sum of |Si| in an input file doesn't exceed 2 * 106
-----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.
import sys

n = int(input())

for i in range(n):
 
 s = input() 
 m = len(s)
  
 if (m == 1):
  sys.stdout.write('NO\n')
 
 elif (m % 2 != 0):

  #check left half
  i = 0
  j = int(m/2)+1
  flag = False
  Flag = True
  while (j < m):
   #print(i,j)
   if (s[i] != s[j]):
    if (not flag):
     flag = True
     i += 1
    else:   
     Flag = False
     break
   else:
    i += 1
    j += 1

  if (not Flag):
   
   #check right half
   i = 0
   j = int(m/2)
   flag = False
   Flag = True
   while (j < m):  
    #print(i,j)
    if (s[i] != s[j]):
     if (not flag):
      flag = True
      j += 1
     else:
      Flag = False
      break
    else:
     i += 1
     j += 1
   if (Flag):
    sys.stdout.write('YES\n')
   else:
    sys.stdout.write('NO\n')

  else:
   sys.stdout.write('YES\n')
  
    
 else:
  if (s[:int(m/2)] == s[int(m/2):]):
   sys.stdout.write('YES\n')
  else:
   sys.stdout.write('NO\n')
import sys

n = int(input())

for i in range(n):
 
 s = input() 
 m = len(s)
  
 if (m == 1):
  sys.stdout.write('NO\n')
 
 elif (m % 2 != 0):

  #check left half
  i = 0
  j = int(m/2)+1
  flag = False
  Flag = True
  while (j < m):
   #print(i,j)
   if (s[i] != s[j]):
    if (not flag):
     flag = True
     i += 1
    else:   
     Flag = False
     break
   else:
    i += 1
    j += 1

  if (not Flag):
   
   #check right half
   i = 0
   j = int(m/2)
   flag = False
   Flag = True
   while (j < m):  
    #print(i,j)
    if (s[i] != s[j]):
     if (not flag):
      flag = True
      j += 1
     else:
      Flag = False
      break
    else:
     i += 1
     j += 1
   if (Flag):
    sys.stdout.write('YES\n')
   else:
    sys.stdout.write('NO\n')

  else:
   sys.stdout.write('YES\n')
  
    
 else:
  if (s[:int(m/2)] == s[int(m/2):]):
   sys.stdout.write('YES\n')
  else:
   sys.stdout.write('NO\n')