Bored after completing all of the statistics handouts for the day, you turn around to take a peek at what Christian is doing. As it turns out, he is working on a list of string puzzles. The goal of the -th puzzle is to transform a string of lowercase letters into the string using the following operation any number of times:
- Select two consecutive occurrences of the same letter and replace them with one occurrence of the next letter in the alphabet. Note that
zis the last letter of the alphabet, so
zzcannot be replaced.
After working on the puzzles for a few minutes, you have a strange suspicion that some of them are impossible. Thus, write a program to determine if it is possible to solve each puzzle.
The sum of over all puzzles does not exceed .
and contain only lowercase letters.
Subtask 1 [30%]
and contain only
Subtask 2 [70%]
No additional constraints.
The first line contains an integer .
The next lines each contain space-separated strings and .
For each puzzle, output
YES if it is solvable or
3 caabdfgg efh zz z dmopc funcontest
YES NO NO