The protagonists of this problem are two great programmers of a certain institution Omanush and OrdinarySheep. On a rainy weekend with nothing to do at hand, Omanush and OrdinarySheep became nostalgic and decided to play a game well known in Bangladesh as Gaaner Koli. But each of them knew songs from many languages other than Bengali, such as English, Bulgarian, Hindi, German and so on. With their vast knowledge, the game became quite unending and they got bored. Since they are problem solvers they quickly understood that they can create a program for optimal game play. They simplified the game in the following way.
There are n songs. A song is a non-empty string of lower case English alphabets. Two players will play the game. First player chooses an arbitrary song to start with and sings a non-empty prefix from it. Second player have to start with a song that starts with the last character of the prefix sang by the first player. He then again sings a non-empty prefix and first player starts a song with the last character.
Let's imagine, there are 2 songs "abc","bac". The first player may sing "ab" from first song. Then second player will sing "b" or "ba" or "bac".
Each song can be used only once, some songs may remain unused. First player can start from any song. If a player is out of moves he loses. If both players play optimally, can the first player win?
If anyone is confused with the rules for playing Gaaner Koli, those are given below:
There are two teams playing the game. First player will start the game with any song he knows and end after singing a certain portion. Then, player 2 will sing a song which he knows and that starts with the last letter of the last song sang by player 1. No song will be used more than once. If a player is unable to sing a song the game ends with the other player as the winner.
First line contains the number of test case T (0 < T < 20). Each of the cases start with one integer n (0 < n ≤ 22). The next n lines contain one song each. The length of each song is at most 100000. Total length of all the songs will be within 1500000.
For each case, print the case number and YES or NO according to the problem. Follow the sample output for precise format.
| Input | Output |
|---|---|
2 2 a b 2 a a | Case 1: YES Case 2: NO |