Almost Palindrome

Given a string s, determine whether it can be transformed into a palindrome by deleting at most one character. For instance, the string abca can become a palindrome if either the character 'b' or 'c' is removed.

Your task is to process multiple test cases. For each test case, output "YES" if the string can be transformed into a palindrome by deleting at most one character, otherwise output "NO".

inputFormat

The first line contains an integer T representing the number of test cases. Each of the next T lines contains a single string s.

Constraints: 1 ≤ T ≤ 10⁵; for each string, 1 ≤ |s| ≤ 10⁵; and the total length of all strings does not exceed 10⁶.

outputFormat

For each test case, print a single line containing "YES" if the string can be transformed into a palindrome by deleting at most one character. Otherwise, print "NO".

1
a

YES