Two girls - Ivica and Marica - play an interesting game.

First, they randomly choose a natural number N. They also define M = 1.

Ivica plays first, then Marica, then Ivica, then Marica and so on.

In each move, a girl has to increase M by 1 or multiply M by 2 (that is, M = M+1 or M = 2*M). The resulting number must not be greater than N.

The loser of the game is the girl who gets M = N. The other girl is, of course, the winner.

Write a program to determine the winner, assuming that both girls play optimally.

Input

In the first line there is an integer T (1 ≤ T ≤ 5), the number of games.

T lines follow. In i^th line there is an integer N (2 ≤ N ≤ 10¹⁵⁾, a chosen number for i^th game.

Output

For each of the T games print the name of the winner.

Example

Input:

4
2
3
4
5

Output:

Marica
Ivica
Marica
Marica