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

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.

见题面

见题面