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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
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 i in range(int(input())):
		n = int(input())
		findWinner(n, 1)
__starting_point()


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

def nbOddEvenprimeFactors(n):
	nb_odd = 0
	nb_even = 0
	while n % 2 == 0:
		n = n / 2
		nb_even += 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		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:
		(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

	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
		elif 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')
		elif findAll(n) == True:
			print('Me')
		else:
			print('Grinch')
except EOFError:
	print(' ')


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


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)


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


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

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.stdin = open('input.txt', 'r')
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')
		elif 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()


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')