Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Old Wives' Game

By reborn · Limits 1s, 256 MB

Kadambari wants to test the brains of the new bride Mrinalini. So she proposed the infamous Old Wives’ Game.

In the game, there are $n$ containers, each filled to the brim with different liquors. $i$’th container has $v_i$ units of liquor in it. There are also cups of different volumes available. Two players take turns. A player in her turn —

• First, chooses a container $i$ which is not empty, i.e. $v_i > 0$.

• Then, chooses a cup with positive integer volume $k$ such that $1 \le k \le v_i$. It is guaranteed that there is a cup of every volume needed.

• Then, starts to drink from the container with the cup in the following manner —

• She fills her cup with liquor from the container and drinks from the cup.

• Once the cup has been emptied, she fills her cup from the container again in the same turn and drinks.

• This filling and drinking procedure goes on unless there is not enough liquor left in the container to fill the cup completely. Note that, the cup must be full. For example, if there is 3 unit liquor left in the container and the cup she chose had a volume of 5 units, she cannot fill or drink anymore and her turn ends.

The player who cannot choose a non-empty container in her turn loses.

Kadambari has allowed Mrinalini to go first. Rabindranath Tagore is anxiously observing the game. Can you predict who will win if the wives play optimally?

Input

The first line consists of an integer $T$ denoting the number of test cases. For each test case —

• Two lines follow. The first line contains an integer $n$, denoting the number of containers.

• The second line contains $n$ space-separated positive integers $v_1, v_2, \dots v_n$ denoting the volume of the containers.

It is guaranteed that —

• $1 \le T \le 10^5$.

• $1 \le n \le 10^5$ and sum of $n$ in all test cases are no greater than $5 \times 10^5$.

• $1 \le v_1, v_2, \dots v_n \le 10^7$.

Output

For each test case, output “Mrinalini” without quotes if Mrinalini wins. Otherwise, if Kadambari wins, output “Kadambari”.

Sample

InputOutput
2
3
2 5 12
2
6 9

Kadambari
Mrinalini


Sample I/O Explanation

Probable gameplay in the first test case —

• Mrinalini picks the 3rd container with 12 units of liquor remaining and chooses a cup of volume 5.

• She fills her cup and drinks. 7 units of liquor remain in the 3rd container.

• She fills her cup and drinks again. 2 units of liquor remain in the 3rd container.

• She can’t fill her cup anymore and thus her turn ends. The quantities in the containers are { 2, 5, 2 }.

• Kadambari picks the 2nd container with 5 units of liquor remaining and chooses a cup of volume 5.

• She fills her cup and drinks. The 2nd container becomes empty.

• Her turn ends since she can’t fill her cup anymore. The quantities in the containers are { 2, 0, 2 }.

• Mrinalini picks the 1st container with 2 units of liquor remaining and chooses a cup of volume 1.

• She fills her cup and drinks. 1 unit of liquor remains in the container.

• She fills her cup and drinks again. The container becomes empty.

• Her turn ends since she can’t fill her cup. The quantities in the containers are { 0, 0, 2 }.

• Kadambari has no other choice but to pick the 3rd container with 2 units of liquor remaining. She chooses a cup of volume 2.

• She fills her cup and drinks. The container becomes empty.

• Her turn ends. The quantities in the containers are { 0, 0, 0 }.

• Mrinalini cannot choose any container to drink from since all the containers are empty. Thus, she loses and in turn, Kadambari wins.

Statistics

47% Solution Ratio

Fizzz_83Earliest, 1M ago

likhon5Fastest, 0.0s

arnab_1810043Lightest, 1.2 MB

NirjhorShortest, 391B