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. (1 ≤ length of string ≤ 10⁵). String will only contain lowercase 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".