L. Two-Player Game
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Insight and Maya are playing a game. Initially, they have an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$ containing only positive integers. Insight moves first, and the two players take turns. In each round, the current player must perform the following steps:

  1. Select an index $$$i$$$ ($$$1 \le i \le n$$$) from the array such that $$$a_i \gt 0$$$;
  2. For all indices $$$j$$$ such that $$$j \neq i$$$, update $$$a_j$$$ to $$$\min(a_j, a_i)$$$;
  3. Subtract $$$1$$$ from the value of $$$a_i$$$.

When it is a player's turn, if all elements in the array are $$$0$$$ (in which case no positive number $$$a_i$$$ can be selected), that player loses the game, and the other player wins. Assuming both players adopt optimal strategies to ensure their own victory, determine who will ultimately win the game.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$), the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 5 \times 10^5$$$), representing the length of the array.

The next line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), representing the initial array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^6$$$.

Output

For each test case, output one line: if Maya has a strategy that allows her to win, output Maya; otherwise, output Insight.

Example
Input
3
3
2 1 3
4
2 1 3 1
4
2 1 1 4
Output
Insight
Insight
Maya