Congratulations !!! You have successfully completed the heist by looting all the gifts in Santa's locker. Now it's time to decide who gets to take all the gifts, you or the Grinch, there will be no splitting. So you and Grinch decide to play a game.
To start the game, an Integer N will be given. The game is played in turns and for each turn, the player can make any one of the following moves:
- Divide N by any of it's odd divisors greater than 1.
- Subtract 1 from N if N is greater than 1.
Divisor of a number includes the number itself.
The player who is unable to make a move loses the game.
Since you are the mastermind of the heist, you get to play the first move.

-----Input-----
The first line contains a single integer T (1 ≤ T ≤ 100) — the number of test cases. The description of the test cases follows.
The only line of each test case contains a single integer — N (1 ≤ N ≤ 109).

-----Output-----
For each test case, print " Me" if you win, and " Grinch" if otherwise (without quotes).

-----Sample Input-----
7
1
2
3
4
5
6
12

-----Sample Output-----
Grinch
Me
Me
Grinch
Me
Grinch
Me

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import math   
  
# Function to find the Largest  
# Odd Divisor Game to check 
# which player wins  
def findWinner(n, k):  
      
    cnt = 0;  
  
    # Check if n == 1 then  
    # player 2 will win  
    if (n == 1): 
        print("Grinch");  
  
    # Check if n == 2 or n is odd  
    elif ((n & 1) or n == 2): 
        print("Me");  
  
    else: 
        tmp = n;  
        val = 1;  
  
        # While n is greater than k and  
        # divisible by 2 keep  
        # incrementing tha val  
        while (tmp > k and tmp % 2 == 0):  
            tmp //= 2;  
            val *= 2;  
              
        # Loop to find greatest  
        # odd divisor  
        for i in range(3, int(math.sqrt(tmp)) + 1):  
            while (tmp % i == 0): 
                cnt += 1;  
                tmp //= i;  
          
        if (tmp > 1): 
            cnt += 1;  
  
        # Check if n is a power of 2  
        if (val == n): 
            print("Grinch");  
  
        elif (n / tmp == 2 and cnt == 1): 
            print("Grinch");  
  
        # Check if cnt is not one  
        # then player 1 wins  
        else: 
            print("Me");  
              
# Driver code  
def __starting_point():  
    for i in range(int(input())):
        n=int(input()) 
        findWinner(n, 1);  
__starting_point()

import math  
def findWinner(n, k):  
      
    cnt = 0;  
  
    if (n == 1): 
        print("Grinch");  
  
    elif ((n & 1) or n == 2): 
        print("Me");  
  
    else: 
        tmp = n;  
        val = 1;  
  
        while (tmp > k and tmp % 2 == 0):  
            tmp //= 2;  
            val *= 2;  
        
        for i in range(3, int(math.sqrt(tmp)) + 1):  
            while (tmp % i == 0): 
                cnt += 1;  
                tmp //= i;  
          
        if (tmp > 1): 
            cnt += 1;  
  
        if (val == n): 
            print("Grinch");  
  
        elif (n / tmp == 2 and cnt == 1): 
            print("Grinch");  
        else: 
            print("Me");  
for i in range(int(input())):
    n = int(input())
    findWinner(n,1)

# cook your dish here
def read_i_l(l=False):
    m = list(map(int, input().strip().split(" ")))
    if l:
        return list(m)
    else:
        return m
def i():
    return int(input().strip())
import math
# A function to print all prime factors of  
# a given number n 
def nbOddEvenprimeFactors(n): 
    nb_odd=0
    nb_even=0
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        n = n / 2
        nb_even+=1
          
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            nb_odd+=1
            n = n / i 
    if n > 2:
        nb_odd+=1
    
    return nb_even, nb_odd              
 
T = i()
for _ in range(T):
    N = i()
    if N == 1:
        print("Grinch")
    elif N == 2:
        print("Me")
    elif N % 2 == 1:
        print("Me")
    else:
        #print(N, nbOddprimeFactors(N))
        e, o = nbOddEvenprimeFactors(N)
        if o == 0 or (e == 1 and o == 1):
            print("Grinch")
        else:
            print("Me")

def is_prime(n):
    return all(n % i for i in range(2, int(n ** 0.5) + 1)) and n >= 2

for _ in range(int(input())):
    n = int(input())

    if n == 1:
        print('Grinch')
        continue

    if n == 2 or n % 2:
        print('Me')
        continue

    if not (n & (n-1)):
        print('Grinch')
        continue

    if is_prime(n // 2):
        print('Grinch')
        continue

    print('Me')


try:
    import math
    # from collection import Counter
    def findAll(n):
        p = 0
        temp = []
        while n % 2 == 0: 
            p += 1  
            n = n / 2
        for i in range(3,int(math.sqrt(n))+1,2): 
            while n % i== 0: 
                if i == 2:
                    p += 1
                else:
                    temp.append(i) 
                n = n / i 
        if n > 2: 
            temp.append(n)
        
        if p == 1:
            if len(temp) != 1:
                return True
            else:
                return False
        else:
            if len(temp) >= 1:
                return True
            else:
                return False
    t = int(input())
    while(t!=0):
        n = int(input())
        if n%2 != 0 and n != 1:
            print("Me")
        elif n%2 != 0 and n== 1:
            print("Grinch")
        elif n== 2:
            print("Me")
        else:
            if findAll(n) == True:
                print("Me")
            else:
                print("Grinch")

except EOFError:
    print(" ")
# This code is contributed by chandan_jnu 


def isprime(n):
    for i in range(2,int(n**(0.5))+1):
        if n%i==0:
            return False
    return True

t=int(input())
while t>0:
    n=int(input())
    x=n & -n

    if n==2:
        print("Me")
    elif (x==2 and isprime(n//x)) or n==1 or x==n :
        print("Grinch")
    else:
        print("Me")
    t-=1

# https://www.geeksforgeeks.org/largest-odd-divisor-game-to-check-which-player-wins/
from sys import stdin, stdout
def winner(n, k):
	cnt = 0; 
	if (n == 1):print("Grinch"); 
	elif ((n & 1) or n == 2):print("Me"); 
	else: 
		tmp = n; 
		val = 1; 
		while (tmp > k and tmp % 2 == 0): 
			tmp //= 2; 
			val *= 2; 
		for i in range(3, int(tmp**0.5) + 1): 
			while (tmp % i == 0): 
				cnt += 1; 
				tmp //= i; 
		if (tmp > 1): 
			cnt += 1; 
		if (val == n): 
			print("Grinch"); 
		elif (n / tmp == 2 and cnt == 1): 
			print("Grinch"); 
		else: 
			print("Me"); 
test = int(stdin.readline())
for _ in range(test):
    n = int(stdin.readline())
    winner(n, 1)

# your code goes here
import math
def isp(n):
	m=2
	p=int(math.sqrt(n));
	while m<=p:
		if(n%m==0):
			break
		m+=1
	return p<m
t=int(input())
while t>0:
	n=int(input())
	if n==1:
	    print("Grinch")
	elif n==2 or n%2==1:
	    print("Me")
	else:
		m=0
		while n%2==0:
			m+=1
			n//=2
		if n==1:
			print("Grinch")
		elif m==1 and isp(n):
			print("Grinch")
		else:
			print("Me")
	t-=1
	        
	            
	            
	        


# cook your dish here
import math
def find(n):
    cnt=0
    if n==0:
        return 1
    if (n == 1): 
        return 0
    elif ((n & 1) or n == 2): 
        return 1
  
    else: 
        tmp = n;  
        val = 1;  
        k=1
        while (tmp > k and tmp % 2 == 0):  
            tmp //= 2;  
            val *= 2
        for i in range(3, int(math.sqrt(tmp)) + 1):  
            while (tmp % i == 0): 
                cnt += 1;  
                tmp //= i;  
        if (tmp > 1): 
            cnt += 1;  
        if (val == n): 
            return 0 
  
        elif (n // tmp == 2 and cnt == 1): 
            return 0 
        else: 
            return 1
t=int(input())
for i in range(t):
    n=int(input())
    if find(n):
        print("Me")
    else:
        print("Grinch")

def isprime(n):
    if n<=1:
        return 0
    if n<=3:
        return 1
    if not n%2 or not n%3:
        return 0
    for i in range(5,int(pow(n,0.5))+1,2):
        if not n%i:
            return 0
    return 1
def abc(n,k):
    if n==0:
        if k%2:
            return True
        return False
    if k%2:
        x=abc(n-1,k+1)
        for j in range(3,n+1,2):
            if not n%j:
                x=x or abc(n//j,k+1)
        return x
    x= abc(n-1,k+1)
    for j in range(3,n+1,2):
        if not n%j:
            x=x and abc(n//j,k+1)
    return x
            
        
t=int(input())
for _ in range(t):
    n=int(input())
    if n&(n-1)==0:
        if n==2:
            print('Me')
        else:
            print('Grinch')
    elif not n%2:
        n=n//2
        if isprime(n):
            print('Grinch')
        else:
            print('Me')
    else:
        print('Me')


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353
# from sys import stdin
# input = stdin.readline
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
try:
    # sys.setrecursionlimit(int(pow(10,6)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass
def pmat(A):
    for ele in A:
        print(*ele,end="\n")
def seive():
    prime=[1 for i in range(10**6+1)]
    prime[0]=0
    prime[1]=0
    for i in range(10**6+1):
        if(prime[i]):
            for j in range(2*i,10**6+1,i):
                prime[j]=0
    return prime
prime=seive()
for _ in range(L()[0]):
    n=L()[0]
    if(n==1):
        print("Grinch")
    elif(n==2):
        print("Me")
    elif(n%2==1):
        print("Me")
    else:
        x=n
        while(x%2==0):
            x//=2
 
        if(x==1):
            print("Grinch")
        else:
            if (n//2)%2==0:
                print("Me")
            else:
                k=0
                for i in range(3,10**5):
                    if(prime[i] and x%i==0):
                        while(x%i==0):
                            x//=i
                            k+=1
                if(x!=1):
                    k+=1
                if(k<=1):
                    print("Grinch")
                else:
                    print("Me")


endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")



from math import sqrt

t = int(input())

while t:
    t -= 1

    n = int(input())

    if n == 1: print("Grinch"); 
    elif (n & 1) or n == 2: print("Me"); 

    else: 
        cnt = 0; 
        tmp = n; 
        val = 1; 

        while (tmp > 1 and tmp % 2 == 0): 
            tmp //= 2; 
            val *= 2; 
            
        for i in range(3, int(sqrt(tmp)) + 1): 
            while (tmp % i == 0): 
                cnt += 1; 
                tmp //= i; 
        
        if tmp > 1: cnt += 1; 

        if val == n: print("Grinch"); 
        elif n / tmp == 2 and cnt == 1: print("Grinch"); 
        else: print("Me")


import math 
def findWinner(n, k): 
	
	cnt = 0; 
	if (n == 1): 
		print("Grinch"); 
	elif ((n & 1) or n == 2): 
		print("Me"); 

	else: 
		tmp = n; 
		val = 1; 
		while (tmp > k and tmp % 2 == 0): 
			tmp //= 2; 
			val *= 2; 
		for i in range(3, int(math.sqrt(tmp)) + 1): 
			while (tmp % i == 0): 
				cnt += 1; 
				tmp //= i; 
		
		if (tmp > 1): 
			cnt += 1; 

		if (val == n): 
			print("Grinch"); 

		elif (n / tmp == 2 and cnt == 1): 
			print("Grinch"); 
		else: 
			print("Me"); 
def __starting_point(): 

	for _ in range(int(input())):
	    n=int(input())
	    findWinner(n, 1); 

__starting_point()