SPCS - Gopu And Palindromes

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:
5
aba
aabaaa
aabbba
aaab
abca

Output:
YES
YES
YES
NO
NO

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".


Added by:praveen123
Date:2013-12-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge

hide comments
2016-12-31 16:08:02
AC in 1 go O(n/2)
2016-03-16 14:24:59 Hemant Prasath
Solved without using paper, pen! AC first go! Cake walk..
2016-02-19 14:38:35 Siddharth Singh
Nice Problem . :)
2016-01-23 12:57:11 Liquid_Science
Iterative O(n^2) dp gives tle,observation gives AC :) feeling dumb!
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 .. :)
2015-08-29 17:29:29
Nice problem, even if it's simple :)
2015-06-13 18:39:13 Abhilash
Simple one
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.