J. Two and Three
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Quintessential Quintuplets is a good show but let's be real here, only two of the quintuplets are actually quintessential.

Nino and Miku are playing a game on an array $$$a$$$ of $$$n$$$ positive integers. In one turn, a player can pick any element in the array and floor divide it by $$$2$$$ or $$$3$$$ as long as the resulting number remains strictly positive. Nino goes first and the player who cannot make a move loses.

A possible game on the array $$$a = [1, 2, 5]$$$ could go as follows:

1. Nino divides $$$a_3$$$ by $$$3$$$ and is left with $$$a_3 = \left \lfloor \frac{5}{3} \right \rfloor = 1$$$ with the array now becoming $$$[1, 2, 1]$$$

2. Miku can then divide $$$a_2$$$ by $$$2$$$ leaving the array as $$$[1, 1, 1]$$$. Note that Miku could not have divided by $$$3$$$ since $$$\left \lfloor \frac{2}{3} \right \rfloor = 0$$$ and that would no longer be positive.

3. Nino then loses since she cannot divide any of the remaining elements by any value. In this game, Nino did not play optimally and lost.

When given the array, assuming both girls play perfectly, who will win?

Input

The first line will contain one integer $$$T$$$, the number of testcases $$$(1 \leq T \leq 10^5)$$$.

The first line of each testcase will contain one integer $$$n$$$, the length of the array $$$(1 \leq n \leq 10^5)$$$.

The following line will contain $$$n$$$ numbers, the array $$$a$$$ $$$(1 \leq a_i \leq 10^9)$$$.

The sum of $$$n$$$ across all testcases will not exceed $$$10^5$$$.

 —

Testcases in subtasks are numbered $$$1 - 20$$$ with samples skipped.

Testcases $$$1 - 5$$$ satisfy $$$n = 1, 1 \leq a_i \leq 10^6$$$.

Testcases $$$6 - 10$$$ satisfy $$$n = 1$$$.

Testcases $$$11 - 15$$$ satsify $$$1 \leq a_i \leq 10^6$$$.

The remaining testcases do not satisfy any additional constraints.

Output

For each testcase output, one string "Nino" or "Miku" (without the quotes) per line, indicating which girl would win with perfect play.

Example
Input
5
3
1 2 5
3
2 3 4
2
3366 3366
1
1000000000
7
1 2 3 4 5 6 7
Output
Nino
Nino
Miku
Nino
Miku
Note

In the first sample the winning strategy is as follows. Nino divides $$$a_3$$$ by $$$2$$$, the array becomes $$$[1, 2, 2]$$$. Whichever value Miku picks to divide by $$$2$$$, Nino can pick the other one and leave Miku out of moves.

In the second sample, if Nino divides $$$a_3$$$ by $$$3$$$, the array becomes $$$[2, 3, 1]$$$. Whatever value Miku picks, Nino can always win.

In the third sample, Miku can mirror any move Nino makes on the other pile. This ensures that Miku can always win.

In the fourth sample, Nino wins. Yeah, I can't be bothered to explain that one.

 —

Idea: 3366, JamesL

Preparation: 3366

Occurrences: Novice 10, Advanced 6