Difficult Game Of String

math10 Intra AUST Programming Co...
Limits 1s, 512 MB

Today we will talk about two friends and a difficult game. For this problem, let's think their names are Mahir and Arnab. Mahir loves his home a lot. So much that if anyone asks him for suggestion to do anything he replies with his legendary dialogue, "Come to my home and we will think about it.". Whether you ask him about how to go to abroad or how to kill cockroach or what is the mass of the sun, he will reply the same "Come to my home and we will think about it.".
Arnab loves to solve difficult problems a lot. Today he is feeling bored. He wants to play a game which is obviously related to a difficult problem. So an idea hits his mind. Knowing Mahir's unique characteristic, Arnab calls him and asks whether he can play a game. And BINGO! Mahir falls in the trap! He says, "Come to my home and we will think about it.". Now as Arnab is in Mahir's home, Mahir cannot refuse to play. So let's go to the description of the difficult game we are talking about.
In the beginning of the game, there will be N strings. On each turn a player chooses any random string R and performs reduce on all string in the list that has R as a prefix. The player who is left with no string to perform reduce on, loses the game. What is reduce? Well it's an operation that removes characters from last from selected string till it has R as its prefix. (Example: Given string "abcba" if anyone chooses "abc" then given string becomes "ab". If anyone chooses "abcb" the given string becomes "abc". If anyone chooses "a" then given string becomes empty).
Remember, Arnab gives the first move and both player play optimally to win the game. No player can choose a string that doesn't let him perform reduce. (Example: For string 'abc', 'def', 'ghi' he cannot choose 'xyz' as it isn't present as prefix of any of the given strings.)

Input

Input starts with an integer T denoting the number of test cases.
Each case starts with a line containing an integer N denoting number of string. Next N lines contain string S (1 <= |S| <= 1000).
Here, T ≤ 30, N ≤ 10^5. You can safely assume that the summation of length of all strings for each test case should be less than or equal to 10^5.

Output

For each case, print the case number and followed by the name of the winner.

Sample

InputOutput
2
2
ab
ad
2
a
b
Case 1: Arnab
Case 2: Mahir

Submit

Login to submit.

Statistics

50% Solution Ratio
NirjhorEarliest, Aug '18
NirjhorFastest, 215680.1s
NirjhorLightest, 21 MB
NirjhorShortest, 813B
Toph uses cookies. By continuing you agree to our Cookie Policy.