Nested Palindromes

A nested palindrome is defined as a string that is a palindrome and can be recursively partitioned into contiguous substrings, each of which is also a palindrome. The process involves checking if the given string is a palindrome. If yes, the string is then split into a prefix and a suffix in every possible way. If any such split results in a prefix that is a palindrome and the suffix that itself is a nested palindrome, then the original string is considered a nested palindrome.

For example, consider the string abcba. It is a palindrome, and a valid partition might be a and bcba, where further recursive checks are performed. An empty string and any single character are trivially considered nested palindromes.

The formal recursive definition can be written as:

$$NP(s)= \begin{cases} \text{true} & \text{if } s \text{ is empty or has one character},\\ \text{false} & \text{if } s \text{ is not a palindrome},\\ \bigvee_{1 \leq i \leq n} \Big( Pal(s[0:i]) \wedge NP(s[i:n]) \Big) & \text{otherwise.} \end{cases} $$

Your task is to determine for each input string whether it is a nested palindrome or not. Output YES if it is a nested palindrome, and NO otherwise.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer T representing the number of test cases.
• The following T lines each contain one string that needs to be checked.

outputFormat

For each test case, print a single line containing YES if the string is a nested palindrome, or NO otherwise. The output is written to standard output (stdout).

## sample

3
abba
abcba
xyz

YES
YES
NO

</p>