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: MEDIUM_HARD
Tags: Constructive algorithms

String algorithms

Greedy algorithms

Data structures

Ad-hoc
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
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()


def isPalin(s):
	return s == s[::-1]
for _ in range(int(input())):
	s = input()
	(i, j) = (0, len(s) - 1)
	ans = 'NO'
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			if isPalin(s[i + 1:j + 1]):
				ans = 'YES'
			elif isPalin(s[i:j]):
				ans = 'YES'
			break
	if i >= j:
		ans = 'YES'
	print(ans)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def checkPalindrome(s):
	return s == s[::-1]

def main():
	for _ in tr():
		s = line()
		if checkPalindrome(s):
			print('YES')
			continue
		possible = False
		n = len(s)
		for i in range(n // 2):
			if s[i] != s[n - i - 1]:
				if checkPalindrome(s[:i] + s[i + 1:]):
					possible = True
				elif checkPalindrome(s[:n - i - 1] + s[n - i:]):
					possible = True
				else:
					break
		print('YES' if possible else 'NO')
main()


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


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())
for j in range(t):
	s = input()
	i = 0
	while i < len(s) // 2 and s[i] == s[-(1 + i)]:
		i += 1
	if i == len(s) // 2:
		print('YES')
	else:
		temp1 = s[:i] + s[i + 1:]
		temp2 = s[:-(1 + i)] + s[len(s) - i:]
		if temp1 == temp1[::-1] or temp2 == temp2[::-1]:
			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 = 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]
	if a == a[::-1] or b == b[::-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])
	for j in range(len(s)):
		c.pop(j)
		x = is_pal(c)
		if x == 1:
			print('YES')
			break
		else:
			count += 1
			c.clear()
			for i in range(len(d)):
				c.append(d[i])
	if count == len(s):
		print('NO')


for _ in range(int(input())):
	s = list(input().strip())
	ans = len(s)
	s2 = s[:]
	for i in range(-(-ans // 2)):
		if s[i] != s[ans - i - 1]:
			s.pop(i)
			s2.pop(ans - i - 1)
			break
	if s == s[::-1] or s2 == s2[::-1]:
		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')


def fun(s, skip):
	i = 0
	j = len(s) - 1
	while i <= j:
		if s[i] != s[j]:
			if skip:
				return fun(s[i + 1:j + 1], 0) or fun(s[i:j], 0)
			else:
				return False
		i += 1
		j -= 1
	return True
for _ in range(int(input())):
	if fun(input(), 1):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	for i in range(len(s) // 2):
		if s[i] != s[len(s) - i - 1]:
			ss = s[:i] + s[i + 1:]
			sss = s[:len(s) - 1 - i] + s[len(s) - i:]
			if ss == ss[::-1] or sss == sss[::-1]:
				print('YES')
				break
			else:
				print('NO')
				break
	else:
		print('YES')


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


import sys

def WordIsPalindrome(theWord):
	return theWord == ''.join(reversed(theWord))
testCase = int(sys.stdin.readline())
while testCase > 0:
	testCase -= 1
	enteredString = sys.stdin.readline().rstrip('\n')
	flagOfWhetherPossible = 0
	while flagOfWhetherPossible == 0 and len(enteredString) != 0:
		if enteredString[0] == enteredString[len(enteredString) - 1]:
			enteredString = enteredString[1:-1]
		elif WordIsPalindrome(enteredString[:-1]) == True or WordIsPalindrome(enteredString[1:]) == True:
			flagOfWhetherPossible = 1
			break
		else:
			flagOfWhetherPossible = 2
			break
	if flagOfWhetherPossible == 2:
		print('NO')
	else:
		print('YES')


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


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


for _ in range(int(input())):
	s = input()
	if s == s[::-1]:
		print('YES')
		continue
	l = 0
	r = len(s) - 1
	while s[l] == s[r]:
		l += 1
		r -= 1
	temp = s[l:r]
	temp1 = s[l + 1:r + 1]
	if temp == temp[::-1] or temp1 == temp1[::-1]:
		print('YES')
	else:
		print('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')


def checkPali(s):
	(left, right) = (0, len(s) - 1)
	while left < right and s[left] == s[right]:
		(left, right) = (left + 1, right - 1)
	return (left, right)

def isPali(x):
	[left, right] = x
	return left >= right

def solve():
	s = input()
	(left, right) = checkPali(s)
	if left >= right or isPali(checkPali(s[left + 1:right + 1])) or isPali(checkPali(s[left:right])):
		print('YES')
	else:
		print('NO')
T = int(input())
for t in range(0, T):
	solve()


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
s = None

def check(i, j, cost):
	if i >= j:
		return cost
	if cost > 1:
		return float('inf')
	elif s[i] == s[j]:
		return check(i + 1, j - 1, cost)
	else:
		return min(check(i + 1, j, cost + 1), check(i, j - 1, cost + 1))
for _ in range(int(input())):
	s = input()
	n = len(s)
	if check(0, n - 1, 0) <= 1:
		print('YES')
	else:
		print('NO')


def ispalendrome(n):
	for i in range(len(n) // 2):
		if n[i] != n[-i - 1]:
			return False
	return True
for _ in range(int(input())):
	S = input()
	i = 0
	j = len(S) - 1
	nf = 0
	fail = []
	while i < j:
		if S[i] != S[j]:
			fail = [i, j]
			break
		i += 1
		j -= 1
	if fail != []:
		if ispalendrome(S[:fail[1]] + S[fail[1] + 1:]) or ispalendrome(S[:fail[0]] + S[fail[0] + 1:]):
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


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


for z in range(int(input())):
	s = input()
	n = len(s)

	def isp(i, j):
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True
	if isp(0, n - 1):
		print('YES')
		continue
	i = 0
	j = n - 1
	while i < j:
		if s[i] != s[j]:
			if isp(i + 1, j) or isp(i, j - 1):
				print('YES')
				break
			print('NO')
			break
		i += 1
		j -= 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	if s == s[::-1]:
		print('YES')
	else:
		for i in range(n // 2):
			if s[i] != s[n - i - 1]:
				break
		for x in [i, n - i - 1]:
			s1 = s[:x]
			s2 = s[x + 1:]
			if s1 + s2 == (s1 + s2)[::-1]:
				print('YES')
				break
		else:
			print('NO')


T = int(input())

def p(s):
	return s == s[::-1]
for t in range(T):
	s = input()
	n = len(s)
	for i in range(n):
		if s[i] != s[n - 1 - i]:
			if p(s[:i] + s[i + 1:]) or p(s[:n - 1 - i] + s[n - i:]):
				print('YES')
			else:
				print('NO')
			break
	else:
		print('YES')


for t in range(int(input())):
	s = input()
	ans = 0
	l = len(s)
	i = 0
	j = l - 1
	flag = 0
	while i < j:
		if s[i] != s[j]:
			flag = 1
			break
		i += 1
		j -= 1
	if flag == 0:
		print('YES')
	else:
		flag = 0
		a = i
		b = j - 1
		while a < b:
			if s[a] != s[b]:
				flag = 1
				break
			a += 1
			b -= 1
		if flag == 0:
			print('YES')
		else:
			flag = 0
			a = i + 1
			b = j
			while a < b:
				if s[a] != s[b]:
					flag = 1
					break
				a += 1
				b -= 1
			if flag == 0:
				print('YES')
			else:
				print('NO')


import sys
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p):
	if type(in_p) == list:
		print(*in_p)
	if type(in_p) == str or type(in_p) == int:
		print(in_p)

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
for _ in range(ii()):
	s = ip()
	i = 0
	j = len(s) - 1
	while i <= j:
		if s[i] == s[j]:
			i = i + 1
			j = j - 1
		else:
			break
	l1 = ispal(i + 1, j, s)
	l2 = ispal(i, j - 1, s)
	if l2 or l1:
		ot('YES')
	else:
		ot('NO')


for _ in range(int(input())):
	s = list(input())
	c = 0
	val = ''
	if s == s[::-1]:
		print('YES')
		continue
	for i in range(len(s)):
		if s[i] != s[len(s) - i - 1]:
			ind = i
			val = s[:ind] + s[ind + 1:]
			if val == val[::-1]:
				c = 1
			ind = len(s) - i - 1
			val = s[:ind] + s[ind + 1:]
			if val == val[::-1]:
				c = 1
			break
	if c == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	t = t - 1
	str = input()
	j = 0
	k = len(str) - 1
	(flag1, flag2) = (False, False)
	while j < k:
		if str[j] == str[k]:
			j = j + 1
			k = k - 1
		else:
			J = j
			K = k - 1
			while J < K:
				if str[J] != str[K]:
					flag1 = True
					J = K
				else:
					J = J + 1
					K = K - 1
			J = j + 1
			K = k
			while J < K:
				if str[J] != str[K]:
					flag2 = True
					J = k
				else:
					J = J + 1
					K = K - 1
			j = k
	if flag1 and flag2:
		print('NO')
	else:
		print('YES')


def check(s, i, j):
	while i < j:
		if s[i] != s[j]:
			return 0
		i += 1
		j -= 1
	return 1
for _ in range(int(input())):
	s = input().strip()
	i = 0
	j = len(s) - 1
	f = 0
	temp = True
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			temp = check(s, i + 1, j) or check(s, i, j - 1)
			f = 1
			break
	if f == 0:
		print('YES')
	elif temp == True:
		print('YES')
	else:
		print('NO')


def ispalin(str1):
	return str1 == str1[::-1]
t = int(input())
for i in range(t):
	exp = input()
	l = len(exp)
	if ispalin(exp):
		print('YES')
	else:
		for j in range(l // 2):
			if exp[j] == exp[-j - 1]:
				continue
			elif ispalin(exp[j:l - j - 1]) or ispalin(exp[j + 1:l - j]):
				print('YES')
				break
			else:
				print('NO')
				break
			print('YES')


def ifpalindrome(x):
	if x == x[::-1]:
		return 'yes'
n = int(input())
res = []
for y in range(n):
	ip = input()
	if ifpalindrome(ip) == 'yes':
		res.append('YES')
	else:
		a = 0
		b = len(ip) - 1
		while ip[a] == ip[b]:
			a += 1
			b -= 1
		temp = ip[0:a] + ip[a + 1:len(ip) + 1]
		temp2 = ip[0:b] + ip[b + 1:len(ip) + 1]
		if ifpalindrome(temp) == 'yes' or ifpalindrome(temp2) == 'yes':
			res.append('YES')
		else:
			res.append('NO')
for x in range(len(res)):
	print(res[x])


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 soln1(s):
	n = len(s)
	if n <= 2:
		return 'YES'
	i = 0
	j = n - 1
	flag = True
	while i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		elif flag:
			flag = False
			if s[i + 1] == s[j]:
				i += 1
			elif s[i] == s[j - 1]:
				j -= 1
			else:
				return 'NO'
		else:
			return 'NO'
	return 'YES'

def check(arr):
	n = len(arr)
	for i in range(n // 2):
		if arr[i] != arr[n - i - 1]:
			return False
	return True

def soln(s):
	s = list(s)
	if check(s):
		return 'YES'
	n = len(s)
	i = 0
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			if check(s[:i] + s[i + 1:]):
				return 'YES'
			elif check(s[:n - i - 1] + s[n - i:]):
				return 'YES'
			else:
				return 'NO'
	return 'NO'
for _ in range(int(input())):
	s = input().strip()
	print(soln(s))


def check(s, i, j):
	while i < j:
		if s[i] != s[j]:
			return 0
		i += 1
		j -= 1
	return 1
flag = int(0)
t = int(input())
while t:
	flag = 0
	s = str(input())
	l = len(s)
	if l == 2:
		print('YES')
	elif l == 3:
		if s[0] == s[1] or s[1] == s[2] or s[2] == s[0]:
			print('YES')
		else:
			print('NO')
	else:
		i = 0
		j = l - 1
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				flag = 1
				if check(s, i, j - 1) == 1 or check(s, i + 1, j) == 1:
					print('YES')
					break
				else:
					print('NO')
					break
		if flag == 0:
			print('YES')
	t -= 1


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)


for i in range(int(input())):
	s = input()
	pos = -1
	if s == s[::-1]:
		print('YES')
	else:
		for i in range(len(s) // 2):
			if s[i] != s[len(s) - i - 1]:
				pos = i
				break
		s1 = s[:pos] + s[pos + 1:]
		s2 = s[:len(s) - pos - 1] + s[len(s) - pos:]
		if s1 == s1[::-1] or s2 == s2[::-1]:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	s = input()
	count = 0
	c = ''
	if s == s[::-1]:
		print('YES')
	else:
		k = len(s)
		(i, j) = (0, k - 1)
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				x1 = s[:i] + s[i + 1:]
				x2 = s[:j] + s[j + 1:]
				if x1 == x1[::-1] or x2 == x2[::-1]:
					print('YES')
					break
				else:
					print('NO')
					break


for _ in range(int(input())):
	s = [str(i) for i in input()]
	n = len(s)
	l = s[:]
	for i in range(-(-len(s) // 2)):
		if s[i] != s[n - i - 1]:
			s.pop(i)
			l.pop(n - i - 1)
			break
	if s == s[::-1] or l == l[::-1]:
		print('YES')
	else:
		print('NO')


def palindrome(s):
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			return False
	return True

def solve(s):
	ind = -9999999
	for i in range(len(s) // 2):
		if s[i] != s[-i - 1]:
			ind = i
			break
	return ind == -9999999 or palindrome(s[ind + 1:len(s) - ind]) or palindrome(s[ind:len(s) - ind - 1])
T = int(input())
for tc in range(T):
	s = input()
	if solve(s):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	if s == s[::-1]:
		print('YES')
	else:
		l = 0
		r = len(s) - 1
		while s[l] == s[r]:
			l += 1
			r -= 1
		s1 = s[l:r]
		s2 = s[l + 1:r + 1]
		if s1 == s1[::-1] or s2 == s2[::-1]:
			print('YES')
		else:
			print('NO')


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def check_palindrome(s, flag=0):
	left = 0
	right = len(s) - 1
	while s[left] == s[right]:
		left += 1
		right -= 1
		if left >= right:
			return True
	if flag == 1 and (check_palindrome(s[left:right]) or check_palindrome(s[left + 1:right + 1])):
		return True
	else:
		return False

def main():
	for _ in tr():
		s = line()
		if check_palindrome(s, 1):
			print('YES')
		else:
			print('NO')
main()


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)
	return r1 if r1 == r2 else None

def alg(s):

	def is_palin(t):
		length = len(t)
		hl = length // 2
		for i in range(hl):
			if t[i] != t[length - i - 1]:
				return False
		return True
	length = len(s)
	hl = length // 2
	for i in range(hl):
		l = s[i]
		r = s[length - 1 - i]
		if l != r:
			if is_palin(s[i:length - 1 - i]) or is_palin(s[i + 1:length - 1 - i + 1]):
				return 'YES'
			else:
				return 'NO'
	return 'YES'

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		s = data.readline().strip()
		res = alg(s)
		print(res)
main()


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 solve():
	i = 0
	j = len(s) - 1
	flag = True
	while i <= j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			temp1 = s[i:j]
			temp2 = s[i + 1:j + 1]
			if temp1 == temp1[::-1] or temp2 == temp2[::-1]:
				break
			else:
				flag = False
				break
	if flag:
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	s = input()
	solve()


for i in range(int(input())):
	s = input()
	if s == s[::-1]:
		print('YES')
	else:
		l = 0
		r = len(s) - 1
		flag = True
		while s[l] == s[r]:
			l += 1
			r -= 1
		temp = s[l:r]
		temp1 = s[l + 1:r + 1]
		if temp == temp[::-1] or temp1 == temp1[::-1]:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	s = input()
	a = 0
	b = len(s) - 1
	f = True
	while a <= b:
		if s[a] == s[b]:
			a += 1
			b -= 1
		else:
			c1 = s[a:b]
			c2 = s[a + 1:b + 1]
			if c1 == c1[::-1] or c2 == c2[::-1]:
				break
			else:
				f = False
				break
	print('YES' if f else 'NO')


for i in range(int(input())):
	s = input()
	rev = s[::-1]
	(l, l_rev) = ('', '')
	(pos, pos_rev) = (0, 0)
	if s == s[::-1]:
		print('YES')
		continue
	for i in range(len(s)):
		if s[i] != rev[i]:
			pos = i
			break
	pos_rev = len(s) - pos - 1
	for i in range(len(s)):
		if i == pos:
			l_rev += s[i]
		elif i == pos_rev:
			l += s[i]
		else:
			l += s[i]
			l_rev += s[i]
	if l == l[::-1] or l_rev == l_rev[::-1]:
		print('YES')
	else:
		print('NO')


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()

def tri(n):
	return n * (n + 1) // 2

def smallest_first(m, n):
	return (min(m, n), max(m, n))

def check_palindrome(s, lives=0):
	(left, right) = (0, len(s) - 1)
	while s[left] == s[right]:
		left += 1
		right -= 1
		if left >= right:
			return True
	if lives == 1 and (check_palindrome(s[left:right]) or check_palindrome(s[left + 1:right + 1])):
		return True
	else:
		return False

def solve(s):
	return 'YES' if check_palindrome(s, 1) else 'NO'

def do_codechef():
	for t in rii():
		print(solve(si()))
do_codechef()
exit()


def is_subsequence(s1, s2):
	i = j = 0
	l = len(s2)
	for j in range(l):
		if i == l - 1:
			break
		if s2[j] == s1[i]:
			i += 1
	return i == l - 1
for _ in range(int(input())):
	s1 = input()
	s2 = s1[::-1]
	if s1 == s2:
		print('YES')
		continue
	l = len(s1)
	if is_subsequence(s1[0:l // 2], s2[0:l // 2 + 1]) or is_subsequence(s2[0:l // 2], s1[0:l // 2 + 1]):
		print('YES')
	else:
		print('NO')


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def ans(s, start, end, num):
	if num > 1:
		return False
	elif start > end:
		return True
	elif s[start] == s[end]:
		return ans(s, start + 1, end - 1, num)
	else:
		return ans(s, start + 1, end, num + 1) or ans(s, start, end - 1, num + 1)
test_cases = int(input())
while test_cases != 0:
	d = input()
	ver = ans(d, 0, len(d) - 1, 0)
	if ver is True:
		print('YES')
	else:
		print('NO')
	test_cases -= 1


def ispal(s):
	return s == s[::-1]

def main():
	T = eval(input())
	for t in range(T):
		s = input()
		left_ptr = 0
		right_ptr = len(s) - 1
		found_different = False
		final_spot = False
		while True:
			if s[left_ptr] != s[right_ptr]:
				found_different = True
				break
			if left_ptr == right_ptr:
				final_spot = True
				break
			if left_ptr + 1 == right_ptr:
				final_spot = True
				break
			left_ptr += 1
			right_ptr -= 1
		good = False
		if found_different:
			remove_left = s[:left_ptr] + s[left_ptr + 1:]
			remove_right = s[:right_ptr] + s[right_ptr + 1:]
			if ispal(remove_left) or ispal(remove_right):
				good = True
		elif final_spot:
			remove_left = s[:left_ptr] + s[left_ptr + 1:]
			remove_right = s[:right_ptr] + s[right_ptr + 1:]
			if ispal(remove_left) or ispal(remove_right):
				good = True
		if good:
			print('YES')
		else:
			print('NO')
main()


def palin(x):
	l = len(x)
	w = int(l / 2)
	for i in range(0, w):
		if x[i] != x[l - i - 1]:
			return 0
		elif i == w - 1:
			return 1
t = int(input())
while t > 0:
	t = t - 1
	x = input()
	temp = list(x)
	l = len(x)
	w = int(l / 2)
	if l == 2:
		print('YES')
	else:
		i = 0
		while temp[i] == temp[l - 1 - i] and i < w:
			i = i + 1
		if palin(x[0:i] + x[i + 1:l]) == 1:
			print('YES')
		elif palin(x[0:l - i - 1] + x[l - (i + 1) + 1:l]) == 1:
			print('YES')
		else:
			print('NO')


import sys

def chk(s, i, j):
	while i < j:
		if s[i] != s[j]:
			return 0
		i += 1
		j -= 1
	return 1

def _input():
	return sys.stdin.readline().strip()

def main():
	for _ in range(int(_input())):
		s = str(_input())
		i = 0
		j = len(s) - 1
		temp = 0
		while i < j:
			if s[i] == s[j]:
				i += 1
				j -= 1
			else:
				x = chk(s, i + 1, j) or chk(s, i, j - 1)
				temp = 1
				break
		if temp == 0:
			print('YES')
		elif x == True:
			print('YES')
		else:
			print('NO')
main()


t = int(input())
for i in range(t):
	s = list(input())
	if len(s) > 1000:
		k = 0
		x = s[::-1]
		for k in range(len(s) // 2):
			if s[k] == s[len(s) - k - 1]:
				continue
			else:
				break
		t = s[:k] + s[k + 1:len(s)]
		x = t[::-1]
		e = s[:len(s) - k - 1] + s[len(s) - k - 1 + 1:len(s)]
		r = e[::-1]
		if t == x or e == r:
			print('YES')
		else:
			print('NO')
	else:
		for k in range(len(s)):
			t = s[:k] + s[k + 1:len(s)]
			if t == t[::-1]:
				print('YES')
				break
		else:
			print('NO')


for i in range(int(input())):
	s = input()
	if s == s[::-1]:
		print('YES')
	else:
		left = 0
		right = len(s) - 1
		flag = True
		while s[left] == s[right]:
			left += 1
			right -= 1
			if left >= right:
				print('YES')
				flag = False
				break
		if flag:
			temp = s[left:right]
			temp1 = s[left + 1:right + 1]
			if temp == temp[::-1] or temp1 == temp1[::-1]:
				print('YES')
			else:
				print('NO')


def is_palindrome(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i = i + 1
		j = j - 1
	return True
T = int(input())
for t in range(T):
	s = input()
	i = 0
	j = len(s) - 1
	res = None
	while i < j and res is None:
		if s[i] != s[j]:
			if not is_palindrome(s[i:j]) and (not is_palindrome(s[i + 1:j + 1])):
				res = False
			else:
				res = True
		i = i + 1
		j = j - 1
	if res is None:
		res = True
	if res:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = list(input().strip())
	ns = len(s)
	new_s = s[:]
	for i in range(-(-ns // 2)):
		if s[i] != s[ns - i - 1]:
			s.pop(i)
			new_s.pop(ns - i - 1)
			break
	if s == s[::-1] or new_s == new_s[::-1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for z in range(t):
	s = list(input())
	if len(s) > 10000:
		i = 0
		j = len(s) - 1
		count = 0
		while i <= j:
			if s[i] != s[j]:
				if s[i] != s[j - 1]:
					j += 1
					count += 1
				elif s[j] != s[i + 1]:
					i -= 1
					count += 1
			i += 1
			j -= 1
		if s == s[::-1]:
			print('YES')
		elif count == 0 and len(s) == 3:
			print('YES')
		elif count == 1 and len(s) != 3:
			print('YES')
		else:
			print('NO')
	else:
		l = 1
		for i in range(len(s)):
			a = s[:i] + s[i + 1:]
			if a == a[::-1]:
				print('YES')
				l = 0
				break
		if l:
			print('NO')


t = int(input())
for i in range(t):
	s = input()
	k = 0
	j = len(s) - 1
	(a, b) = ('', '')
	while k <= j:
		if s[k] != s[j]:
			a = s[:k] + s[k + 1:]
			b = s[:j] + s[j + 1:]
			break
		k = k + 1
		j = j - 1
	if a == a[::-1] or b == b[::-1]:
		print('YES')
	else:
		print('NO')


def palin(s):
	flag = 0
	pos = 0
	for i in range(len(s) // 2):
		if s[i] != s[-1 - i]:
			flag = 1
			pos = i
			break
	if flag == 1:
		return pos
	else:
		return -1
t = int(input())
for i in range(t):
	ns = ''
	s = input()
	ok = palin(s)
	if ok == -1:
		print('YES')
	else:
		for j in range(len(s)):
			if j != ok:
				ns += s[j]
		ok1 = palin(ns)
		if ok1 == -1:
			print('YES')
		else:
			new = ''
			oppo = len(s) - ok - 1
			for j in range(len(s)):
				if j != oppo:
					new += s[j]
			if palin(new) == -1:
				print('YES')
			else:
				print('NO')


def P(s, n):
	for i in range(n // 2):
		if s[i] != s[n - i - 1]:
			return False
	return True

def isP(s, n):
	(i, j) = (0, n - 1)
	while i < j:
		if s[i] == s[j]:
			i += 1
			j -= 1
		else:
			if P(s[i:j], j - i) or P(s[i + 1:j + 1], j - i):
				return True
			return False
	return True
for _ in range(int(input())):
	s = list(input().strip())
	if isP(s, len(s)):
		print('YES')
	else:
		print('NO')


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


from collections import Counter
for _ in range(int(input())):
	l = input()
	val = 0
	length = len(l) // 2
	i = 0
	j = len(l) - 1
	flag = False
	count = 0
	count1 = 0
	if l == l[::-1]:
		print('YES')
		continue
	while i < length:
		if l[i] != l[j]:
			count = i
			count1 = j
			break
		i += 1
		j -= 1
	string = l[:count] + l[count + 1:]
	string2 = l[:count1] + l[count1 + 1:]
	if string == string[::-1] or string2 == string2[::-1]:
		print('YES')
	else:
		print('NO')