Given a string s. Can you make it a palindrome by deleting exactly one character? Note that size of the string after deletion would be one less than it was before. 

-----Input-----
First line of the input contains a single integer T denoting number of test cases.
For each test case, you are given a single line containing string  s. 

-----Output-----
For each test case, print YES or NO depending on the answer of the problem. 

-----Constraints-----
Subtask 1, 35 points 
-  1 ≤ T ≤ 100
- 2 ≤  size of string s ≤ 1000
-  String s contains lowercase English alphabets (ie. from 'a' to 'z').

Subtask 2, 65 points 
- 2 ≤  size of string s ≤ 10^5
-  Sum of size of string s over all the input test cases won't exceed 10^6
-  String s contains lowercase English alphabets (ie. from 'a' to 'z').

-----Example-----
Input:
4
aaa
abc
abdbca
abba

Output:
YES
NO
YES
YES

-----Explanation-----
Example case 1. Delete any one 'a', resulting string is "aa" which is a palindrome.
Example case 2. It is not possible to delete exactly one character and having a palindrome.
Example case 3. Delete 'c', resulting string is "abdba" which is a palindrome. 
Example case 4. Delete 'b', resulting string is "aba" which is a palindrome.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 s=str(input())
 n=len(s)
 k=s[::-1]
 a,b="",""
 for i in range(n):
  if s[i]!=k[i]:
   a+=s[i+1:]
   b+=k[i+1:]
   break
  else:
   a+=s[i]
   b+=k[i]
 #print(a,b)
 if a==a[::-1] or b==b[::-1]:
  print("YES")
 else:
  print("NO")


for _ in range(int(input())):
 s=str(input())
 k=s[::-1]
 n=len(s)
 grid=[[0]*(n+1) for i in range(n+1)]
 for i in range(n+1):
  for j in range(n+1):
   if i==0 or j==0:
    grid[i][j]=0
   elif s[i-1]==k[j-1]:
    grid[i][j]=grid[i-1][j-1]+1
   else:
    grid[i][j]=max(grid[i-1][j],grid[i][j-1])
 if n-grid[n][n]<=1:
  print("YES")
 else:
  print("NO")
  
  


# cook your dish here
def solve():
 s=input().strip()
 i=0
 j=len(s)-1
 a=''
 b=''
 while i<=j:
  if s[i]!=s[j]:
   a=s[:i]+s[i+1:]
   b=s[:j]+s[j+1:]
   break
  i+=1
  j-=1
 if a==a[::-1] or b==b[::-1]:
  print("YES")
 else:
  print("NO")

test=int(input())
for _ in range(test):
 solve()

def solve():
 s=input().strip()
 i=0
 j=len(s)-1
 a=''
 b=''
 while i<=j:
  if s[i]!=s[j]:
   a=s[:i]+s[i+1:]
   b=s[:j]+s[j+1:]
   break
  i+=1
  j-=1
 if a==a[::-1] or b==b[::-1]:
  print("YES")
 else:
  print("NO")

def __starting_point():
 t=int(input())
 for _1 in range(t):
  solve()
__starting_point()

import sys

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def input(): return sys.stdin.readline().strip()


for _ in range(int(input())):
 flag1=1
 flag2=1
 s = input()
 i = 0
 j = len(s)-1
 while(i<=j):
  if(s[i]!=s[j]):
   break
  i=i+1
  j=j-1
 if(i>j):
  print('YES')
  continue
 k=i
 m=j
 i=i+1
 while(i<=j):
  if(s[i]!=s[j]):
   flag1=0
   break
  i += 1
  j -= 1
 i=k
 j=m-1
 while(i<=j):
  if(s[i]!=s[j]):
   flag2=0
   break
  i += 1
  j -= 1
  
 if(flag1 or flag2):
  print('YES')
 else:
  print('NO')

def isp(s):
 return s==s[::-1]
for _ in range(int(input())):
 s=input()
 s=list(s)
 if s==s[::-1]:
  print('YES')
  continue 
 f=0 
 n=len(s)
 for i in range(n):
  if s[i]!=s[n-i-1]:
   ind=i 
   if isp(s[:ind]+s[ind+1:]):
    f=1 
   ind=n-i-1 
   if isp(s[:ind]+s[ind+1:]):
    f=1 

   break 
 print('YES' if f else 'NO')

for _ in range(int(input())):
 S=list(input())
 N=len(S)
 c=False
 for i in range(N):
  p=S.copy()
  del p[i:i+1]
  if p==p[::-1]:
   c=True
   break
 if c:
  print('YES')
 else:
  print('NO')

from collections import Counter
for _ in range(int(input())):
 data = input().strip()
 each_char_count = Counter(data)
 count_ = 0
 ans = 'YES'
 for i in each_char_count:
  if each_char_count[i]%2!=0:
   count_ += 1
  if count_ > 2:
   ans = 'NO'
   break
 print(ans)


from collections import Counter
for _ in range(int(input())):
 data = input()
 each_char_count = Counter(data)
 count_ = 0
 ans = 'YES'
 for i in each_char_count:
  if each_char_count[i]%2!=0:
   count_ += 1
  if count_ > 2:
   ans = 'NO'
   break
 print(ans)


from collections import Counter
for _ in range(int(input())):
 data = input()
 each_char_count = Counter(data)
 count_ = 0
 status = False
 for i in each_char_count:
  if each_char_count[i]%2!=0:
   count_ += 1
  if count_ > 2:
   status = True
   break
 if status == False:
  print("YES")
 else:
  print("NO")


def pal(s):
 f=0
 for i in range(len(s)//2):
  if s[i]!=s[len(s)-i-1]:
   f=1
   break
 if f==0:
  return 1
 else:
  return 0
for _ in range(int(input())):
 s=input()
 a=pal(s)
 if a==1:
  print("YES")
 else:
  f=0
  for i in range(len(s)-1):
   s2=s[0:i]+s[i+1:len(s)]
   a=pal(s2)
   if a==1:
    f=1
    break
  if f==0:
   print("NO")
  else:
   print("YES")

def pal(s):
 f=0
 for i in range(len(s)//2):
  if s[i]!=s[len(s)-i-1]:
   f=1
 if f==0:
  return 1
 else:
  return 0
for _ in range(int(input())):
 s=input()
 a=pal(s)
 if a==1:
  print("YES")
 else:
  f=0
  for i in range(len(s)-1):
   s2=s[0:i]+s[i+1:len(s)]
   a=pal(s2)
   if a==1:
    f=1
    break
  if f==0:
   print("NO")
  else:
   print("YES")

def palindrome(ch):
 t=False
 if ch==ch[::-1]:
  t=True
 return t
def deel(ch,i):
 gh=ch[:i]+ch[i+1:]
 return gh
for i in range(int(input())):
 ch=input()
 f=0
 for j in range(len(ch)):
  
  gh=deel(ch,j)
  if palindrome(gh):
   f=1
   print('YES')
   break
 if f==0:
  print('NO')
  


t = int(input())


def fun(s):
 for i in range(len(s) - 1):
  s1 = s[:i] + s[i+1:]
  if s1 == s1[::-1]:
   return True

 s1 = s[:len(s)-1]
 if s1 == s1[::-1]:
  return True
 return False


for _ in range(t):
 s = input()
 if fun(s):
  print("YES")
 else:
  print("NO")

# cook your dish here
t = int(input())


def fun(s):
 for i in range(len(s) - 1):
  s1 = s[:i] + s[i+1:]
  if s1 == s1[::-1]:
   return True

 s1 = s[:len(s)]
 if s1 == s1[::-1]:
  return True
 return False


for _ in range(t):
 s = input()
 if fun(s):
  print("YES")
 else:
  print("NO")

def isp(s):
 return s==s[::-1]
for _ in range(int(input())):
 s=input()
 s=list(s)
 if s==s[::-1]:
  print('YES')
  continue 
 f=0 
 n=len(s)
 for i in range(n):
  if s[i]!=s[n-i-1]:
   ind=i 
   if isp(s[:ind]+s[ind+1:]):
    f=1 
   ind=n-i-1 
   if isp(s[:ind]+s[ind+1:]):
    f=1 

   break 
 print('YES' if f else 'NO')

def is_pal(s):
 if len(s)==1:
  return 1
 else:
  count=0
  for i in range(int(len(s)/2)):
   if s[i]==s[len(s)-1-i]:
    count+=1
  if count==int(len(s)/2):
   return 1
  else:
   return 0
t = int(input())
for i in range(t):
 count=0
 s = input()
 c = list()
 d = list()
 f = 0
 if is_pal(s):
  print('YES')
 else:
  for j in range(len(s)):
   c.append(s[j])
   d.append(s[j])
  
  n = len(s)
  for j in range(n):
   if s[j]!=s[n-j-1]:
    c.pop(j)
    x = is_pal(c)
    if x==1:
     f=1
     break
    else:
     c.clear()
     for i in range(len(d)):
      c.append(d[i])
     c.pop(n-j-1)
     x = is_pal(c)
     if x==1:
      f=1
      break
     else:
      c.clear()
      for i in range(len(d)):
       c.append(d[i])
  if f==1:
   print('YES')
  else:
   print('NO')


def is_pal(s):
 if len(s)==1:
  return 1
 else:
  count=0
  for i in range(int(len(s)/2)):
   if s[i]==s[len(s)-1-i]:
    count+=1
  if count==int(len(s)/2):
   return 1
  else:
   return 0
t = int(input())
for i in range(t):
 count=0
 s = input()
 c = list()
 d = list()
 for j in range(len(s)):
  c.append(s[j])
  d.append(s[j])
#     print(c)
#     print(d)
 for j in range(len(s)):
  c.pop(j)
  x = is_pal(c)
  if x==1:
   print('YES')
   break
  else:
#             print(c)
   count+=1
   c.clear()
   for i in range(len(d)):
    c.append(d[i])
#             print(c)
 if count==len(s):
  print('NO')

t = int(input())
for T in range(t):
 s = input()
 alpha = [0] * 26
 odd = 0
 for i in s:
  alpha[ord(i) - 97] += 1
 for i in range(26):
  alpha[i] = alpha[i] % 2
  if alpha[i] == 1:
   odd += 1
 if odd <= 2:
  print("YES")
 else:
  print("NO")


def isp(s):
 return s==s[::-1]
for _ in range(int(input())):
 s=input()
 s=list(s)
 if s==s[::-1]:
  print('YES')
  continue 
 f=0 
 n=len(s)
 for i in range(n):
  if s[i]!=s[n-i-1]:
   ind=i 
   if isp(s[:ind]+s[ind+1:]):
    f=1 
   ind=n-i-1 
   if isp(s[:ind]+s[ind+1:]):
    f=1 

   break 
 print('YES' if f else 'NO')

def isp(s):
 return s==s[::-1]
for _ in range(int(input())):
 s=input()
 s=list(s)
 if s==s[::-1]:
  print('YES')
  continue 
 f=0 
 n=len(s)
 for i in range(n):
  if isp(s[:i]+s[i+1:]):
   f=1 
   break 
 print('YES' if f else 'NO')

from collections import Counter
for _ in range(int(input())):
 s=input()
 Length=len(s)
 List=list(s)
 even=0
 odd=0
 Dict=Counter(List)
 Len=len(Dict)
 if(Length%2!=0):
  for i in Dict:
   if(Dict[i]%2==0):
    even+=1
   else:
    odd+=1
  if(odd==1):
   print("YES")
  else:
   print("NO")
   
 else:
  for i in Dict:
   if(Dict[i]%2==0):
    even+=1
   else:
    odd+=1
  if(odd==0 or odd==2):
   print("YES")
  else:
   print("NO")

   
 
 


from collections import Counter
for _ in range(int(input())):
 s=input()
 Length=len(s)
 List=list(s)
 even=0
 odd=0
 Dict=Counter(List)
 Len=len(Dict)
 if(Length%2!=0):
  for i in Dict:
   if(Dict[i]%2==0):
    even+=1
   else:
    odd+=1
  if(odd==1):
   print("YES")
  else:
   print("NO")
   
 else:
  for i in Dict:
   if(Dict[i]%2==0):
    even+=1
   else:
    odd+=1
  if(odd<=2):
   print("YES")
  else:
   print("NO")

   
 
 


for _ in range(int(input())):
 s=input()
 p=int(len(s))
 r=list(s)
 w=0
 if r==r[::-1]:
  print('YES')
 else:
  for i in range(p):
   w=2
   r.pop(i)
   if r==r[::-1]:
    w=1
    break
   r=list(s)
 if w==1:
  print("YES")
 elif w==2:
  print("NO") 


for _ in range(int(input())):
 s=input()
 p=len(s)
 r=list(s)
 w=0
 if r==r[::-1]:
  print('YES')
 else:
  for i in range(p):
   w=2
   r.pop(i)
   if r==r[::-1]:
    w=1
    break
   r=list(s)
 if w==1:
  print("YES")
 elif w==2:
  print("NO")