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
a_nkyy123: 2022-08-11 11:04:08

How o/p for 11 is Ivica?

pavan_kumar1: 2017-06-30 16:04:04

Admin please check the submission id:19708414
its giving a WA......... I am not able to understand what am I missing.

I got it..... :-)

Last edit: 2017-06-30 16:35:59
Adrian Satja Kurdija: 2016-02-07 20:26:19

@Shubham Porlikar: try this one

5
2211
41481
8331
99999
88888

Output should be:

Ivica
Ivica
Ivica
Marica
Marica

Shubham Porlikar: 2015-01-06 21:34:04

@Adrian Satja Kurdija Can you please help with id 13347146?

vabs: 2014-04-14 06:11:30

someone plz suggest some more inputs , repeatedly getting wa

adze: 2014-04-10 10:32:36

@STAYING_ALIVE:
Yes, there is some confusion in the test cases. The thing is, Ivica always plays first.

Last edit: 2014-04-01 19:11:42
RISHABH JAIN: 2014-04-10 10:32:36

My 250th problem :)

vabs: 2014-04-10 10:32:36

i m a bit confused about the fourth sample test case - if the moves are +1(m) , +1(i) , +1(m), +1(i) ivica wins but for moves +1(m) , x2(i),+1(m) marica wins . so if the state of winning depends on ivica , why will x2 be choosen by her

785227: 2014-04-10 10:32:36

What is the answer for 101 ?

Shaka Shadows: 2014-04-10 10:32:36

Beautiful pattern Adrian!!!
@Rahul Shah the answer for both 11 and 33 is Ivica.

Last edit: 2013-08-07 12:56:47

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