One-Deletion Palindrome Check

You are given a string and you need to determine whether it can become a palindrome by removing at most one character. A palindrome is a string that reads the same backwards as forwards. In other words, for a given string \(s\), you are allowed to delete at most one character such that the resulting string \(s'\) satisfies \(s' = \text{reverse}(s')\).

For example:

• "abca" can become "aba" (by removing 'c') which is a palindrome → output YES.
• "racecar" is already a palindrome → output YES.
• "abc" cannot be rearranged into a palindrome with one removal → output NO.

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

The key observation is that while traversing the string from both ends, if a mismatch is found, then one of the two characters may be removed to check if the remaining substring forms a palindrome. The decision should be made efficiently.

Note: Use the following definition of a palindrome: a string \(s\) of length \(n\) is a palindrome if \(s_i=s_{n-i+1}\) for every valid index \(i\). In our formulas, indices are 1-based.

inputFormat

The first line of input contains an integer \(N\) which denotes the number of test cases. Each of the following \(N\) lines contains a non-empty string \(s\) consisting of lowercase English letters.

Input Format:

N
s_1
s_2
...
s_N

outputFormat

For each test case, output a single line containing either YES if the string can be converted into a palindrome by removing at most one character, or NO otherwise.

Output Format:

result_1
result_2
...
result_N

## sample

3
abca
racecar
abc

YES
YES
NO

</p>