Gopu loves palindromes. A palindrome is a string which is same even when it is reversed. eg. aba, a, abba are palindromes whereas, ab is not a palindrome.
Once Gopu was playing with string s, he thought of whether he can change this string into a palindrome or not.
A "cool operation" takes some substring of string with the property that all the characters in the substring should be same. Let us say that substring has size L. Then he can reduce the size of this substring by at least 0 and at most L - 1. e.g. string is abbb, He can change substring bbb into b, bb, bbb (corresponding to not changing it at all) which will make the string s into ab, abb, abbb respectively.
He can apply a "cool operation" as many times as he wishes.
Find out whether he can convert the string into a palindrome or not?
Output "YES" if possible, else output "NO".
Input
First line of input contains number of test cases T, (1 <= T <= 100).
For each test case, there is a single line representing the string with which Gopu is playing with. (length of string >= 1 and <= 10^5). String will only contain small letters of English alphabet i.e. 'a' to 'z'.
Output
For each test case output a single line containing "YES" or "NO" (without quotes) respectively to situation whether he can convert given string into palindrome or not?
Example
Input:5abaaabaaaaabbbaaaababcaOutput:YESYESYESNONO
Explanation
For first test case string "aba", string is already a palindrome, so no need to apply "cool operation".
For second test case string "aabaaa", take aaa and convert it into aa, So string becomes aabaa which is a palindrome.
For fifth test case string "abca", Gopu can not convert it into palindrome despite applying any "cool operation".
 | vengatesh15: 2016-12-31 16:08:02 AC in 1 go O(n/2) |
 | Hemant Prasath: 2016-03-16 14:24:59 Solved without using paper, pen! AC first go! Cake walk.. |
 | Siddharth Singh: 2016-02-19 14:38:35 Nice Problem . :) |
 | Liquid_Science: 2016-01-23 12:57:11 Iterative O(n^2) dp gives tle,observation gives AC :) feeling dumb! |
 | dwij28: 2015-09-30 18:11:06 Recursive solution gives sigabrt error in cpp and TLE in python.. Did it iteratively in cpp after several runtime errors .. Relief .. :) |
 | hodobox: 2015-08-29 17:29:29 Nice problem, even if it's simple :) |
 | Abhilash: 2015-06-13 18:39:13 Simple one |
