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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
def check_equal(a,b):
 index=0
 for i in a:
  while index<len(b) and i != b[index]:
   index+=1
  if(index>=len(b)):
   return False
  index+=1 
 return True
def Dob_String(n):
 size=len(n)
 midpoint=size//2
 if(check_equal(n[0:midpoint],n[midpoint:size])):
  return("YES")
 elif(size%2!=0 and check_equal(n[midpoint+1:size],n[0:midpoint+1])):
  return("YES")
 else:
  return("NO")
T=int(input()) 
for _ in range(T):
 n=input()
 if(len(n)>1):
  print(Dob_String(n))
 else:
  print("NO")

# cook your dish here
t = int(input())
for _ in range(t):
 s = input()
 if len(s) % 2 == 0:
  ok = True
  for i in range(len(s) // 2):
   if s[i] != s[i + len(s) // 2]:
    ok = False
    break
  if ok:
   print("YES")
  else:
   print("NO")
 elif len(s) == 1:
  print("NO")
 else:
  idx1 = 0
  idx2 = len(s) // 2
  ok = False
  while idx1 < len(s) // 2 and idx2 < len(s):
   if s[idx1] != s[idx2]:
    idx2 += 1
   else:
    idx1 += 1
    idx2 += 1
  if idx1 == len(s) // 2:
   ok = ok or True
  idx1 = len(s) // 2 + 1
  idx2 = 0
  while idx1 < len(s) and idx2 <= len(s) // 2:
   if s[idx1] != s[idx2]:
    idx2 += 1
   else:
    idx1 += 1
    idx2 += 1 
  if idx1 == len(s):
   ok = ok or True
  if ok:
   print("YES")
  else:
   print("NO")


# cook your dish here
import math
import numpy as np

import pandas as pd
import itertools
import collections
from collections import Counter

import copy as deepcopy



def is_double(s):
 n = len(s)
 if n%2 == 1:
  return False
 elif n == 0:
  return False
  
 else:
  
  
  if s[:n//2] != s[n//2:n]:
   




   return False
  else:
   return True
  
 
     
     
    
    





 
try:
 
 T = int(input())
 for l in range(T):
  
   
   
  s = input()
  n = len(s)
  
  if is_double(s):
   print("YES")
  else:
   flag = False
   for i in range(n):
    if is_double(s[:i]+s[i+1:]):
     flag = True
     break
   if flag:
    print("YES")
   else:
    print("NO")
    
  
  
       
       
       
   
except EOFError:
 pass

  
 



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')

f = 0
t = int(input())
while t>0:
 t-=1
 o =0
 s = input()
 s = list(s)
 n = len(s)
 if len(s) == 1:
  print("NO")
  continue
 if len(s) % 2 == 1:
  for i in range(n):
   ls = s.copy()
   ls.pop(i)
   if ls[0:int((len(ls))/2)] == ls[int((len(ls))/2):int(len(ls))]:
    print("YES")
    o = 1
    break
  if o == 0:
   print("NO")

 else:
  if s[0:int((len(s))/2)] == s[int((len(s))/2):int(len(s))]:
   print("YES")
  else:
   print('NO')

# cook your dish here
t = int(input())
while t > 0:
 s = input()
 n = len(s)
 f = 0
 if n == 1:
  f = 0
 else:
  if len(s) % 2 == 0:
   if s[0:n // 2] == s[n // 2:]:
    f = 1
  else:
   l = (n + 1)//2
   for i in range(l):
    if i == l-1:
     a = s[0 : i] + s[i + 1 : len(s)]
     h = len(a) // 2
     if a[0 : h] == a[h : len(a)]:
      f = 1
      break
     else:
      f = 0
      break
    if s[i] == s[l + i]:
     pass
    else:
     a = s[0:i]+s[i + 1 :len(s)]
     if a[0 : len(a) // 2] == a[len(a) // 2 : len(a)]:
      f = 1
      break
     else:
      a = s[0 : l + i] + s[l + 1 + i : len(s)]
      if a[0 : len(a) // 2] == a[len(a) // 2:len(a)]:
       f = 1
       break
 if f == 0:
  print('NO')
 else:
  print('YES')
 t -= 1

for _ in range(int(input())):
 s = input()
 s = list(s)
 s1 = s
 f = 0
 l = len(s)
 if l >= 2:
  for i in range(l):
   if l % 2 == 0:
    ln = l
    tp1 = s1[:(ln//2)]
    tp2 = s1[(ln//2):]
    if str(tp1) == str(tp2):
     f = 1
     break
   else:    
    if i == 0:
     tmp = s1[i+1:]
     ln = l - 1
     tp1 = tmp[:(ln//2)]
     tp2 = tmp[(ln//2):]
     if str(tp1) == str(tp2):
      f = 1
      break
    else:
     tmp = s1[:i]
     tmp2 = s1[i+1:]
     temp = tmp + tmp2
     ln = l - 1
     tp1 = temp[:(ln//2)]
     tp2 = temp[(ln//2):]
     if str(tp1) == str(tp2):
      f = 1
      break
  if f == 1:
   print("YES")
  else:
   print("NO")
 elif l == 1:
  print("NO")
  


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')

t = int(input())
for i in range(t):
 s = input()
 if len(s) == 0 or len(s) == 1:
  print("NO")
 else:
  if len(s)%2==0:
   flag = False
   half = int(len(s)/2)
   if s[0:half]== s[half:len(s)]:
    flag = True
   else:
    pass
  else:
   flag = False
   for j in range(len(s)):
    news = s[0:j]+s[j+1:len(s)]
    half = int(len(news) / 2)
    if news[0:half] == news[half:len(news)]:
     flag = True
     break
    else:
     continue
  if flag:
   print("YES")
  else:
   print("NO")

t = int(input())
for i in range(t):
 s = input()
 if len(s)==0:
  print("NO")
 else:
  if len(s)%2==0:
   flag = False
   half = int(len(s)/2)
   if s[0:half]== s[half:len(s)]:
    flag=True
   else:
    pass
  else:
   flag = False
   for j in range(len(s)):
    news = s[0:j]+s[j+1:len(s)]
    if len(news) == 0:
     flag = False
     break
    if len(news) % 2 == 0:
     half = int(len(news) / 2)
     if news[0:half] == news[half:len(news)]:
      flag = True
      break
     else:
      continue
  if flag:
   print("YES")
  else:
   print("NO")

from collections import Counter 
def is_spcl(s,n):
 return s[:n//2]==s[n//2:] 
for _ in range(int(input())):
 s=input()
 n=len(s)
 if len(s)==1:
  print('NO')
  continue
 if s[0:n//2]==s[n//2:]:
  print('YES')
  continue 
 f=0 
 for i in range(0,n):
  if is_spcl(s[0:i]+s[i+1:],n-1):
   f=1 
   break 
 print('YES' if f else 'NO')