Determine Quasi-Palindromes

Given a list of strings, determine if each string is a quasi-palindrome. A quasi-palindrome is a string that can be transformed into a palindrome by removing at most one character. More formally, a string ( s ) is a quasi-palindrome if there exists at most one index ( i ) such that by removing the character at that index, the resulting string is a palindrome (i.e., it reads the same forwards and backwards).

For example, for the string "abca", by removing the character 'c', the string becomes "aba", which is a palindrome.

inputFormat

The first line contains an integer ( n ) representing the number of strings. Each of the following ( n ) lines contains a single string ( s ). Note that the string may be empty.

outputFormat

Output ( n ) lines. For each string, print "YES" if it is a quasi-palindrome, otherwise print "NO".## sample

3
abca
abccba
abcdef

YES
YES
NO