Almost Palindrome

This problem asks you to determine whether a given string can be transformed into a palindrome by removing at most one character. A palindrome is a string that reads the same forwards and backwards. Mathematically, a string S of length n is a palindrome if:

\(S[i] = S[n-i+1]\) for all \(1 \leq i \leq n\).

If the string is not a palindrome, you are allowed to remove one character to try to achieve this property. Your task is to determine, for each input string, whether it is possible to turn it into a palindrome with at most one removal.

Note that an empty string and a single character string are trivially palindromic.

inputFormat

The input begins with an integer T representing the number of test cases. Each of the following T lines contains a string S consisting of lowercase Latin characters ('a' to 'z').

Constraints:

• \(T \leq 10^4\)
• \(|S| \leq 10^5\)
• The total length of all strings in a test file does not exceed \(10^6\).

outputFormat

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

## sample

2
abca
abc

YES
NO

</p>