GAME3 - Yet Another Fancy Game

no tags 

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 ith line there is an integer N (2 ≤ N ≤ 1015), a chosen number for ith 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

hide comments
Rahul Shah: 2014-04-10 10:32:36

whats the o/p for 2 33 11

Last edit: 2013-01-18 12:00:21
Aman Gupta: 2014-04-10 10:32:36

How long were they playing this game?!
Assuming each turn took 1s.
~10^15s=3.16888 x 10^7 years!
haha

Last edit: 2012-10-12 06:45:29
eddy: 2014-04-10 10:32:36

suggest some more inputs


Added by:Adrian Satja Kurdija
Date:2011-10-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:originated from a mathematical problem