Sally loves palindromes and has made it her goal to memorize every palidrome in existence. A palindrome is a string that is the same whether it is read forwards or backwards. For example, the following strings are all palindromes:
A man, a plan, a canal, panama!(If we ignore punctuation)
Sally wants to read the dictionary and memorize every palindrome. Help her figure out whether certain words are palindromes.
The first line of input provides the number of test cases, ~T~ ~(1 \le T \le 100)~. ~T~ test cases follow. Each test case consists of one word containing exclusively uppercase letters.
For each test case, your program should output one line containing
YAY if the word is
a palindrome, or
4 DAD TOOT DOORKNOB RACECAR
YAY YAY NAY YAY