Read problems statements in Mandarin Chinese and Russian as well. 

Mike and his friend Tom are playing a very interesting game right now. Here is the description of the game:

		Initially, there is a positive integer N written on the desk, which is strictly greater than 1;
		Mike makes the first move, then players make moves alternatively;
		On each move the current player can either decrease the number on the desk by 1, or divide it by one of it's divisors except itself and 1; It's forbidden to decrease the number if it's equal to 1;
		If the current player can't make a move, then he loses. In other words, if there is "1" written on the desk right before his move, then he loses.
	
You are given a number N. You need to determine the winner of the game, if N is the number written of the desk initially. You may assume, that both players play optimally.

------ Input ------ 

There are multiple test cases in the input. The first line of the input contains one integer T, denoting the number of test cases in the input.

The next T lines contain one integer each, denoting the initial number of the game.
All the test cases are independent and must be considered separately!
 
------ Output ------ 

Your output should contain exactly T lines, each contains the name of the winner(Mike or Tom) of the corresponding game. You should output the verdicts of the games in the order they appear in the input.
 
------ Constraints ------ 

1 ≤ T ≤ 10 000;
2 ≤ N ≤ 10^{8}, for each test case appeared in the input.

------ Example ------ 

Input:
4 
5 
3 
2 
4

Output:
Tom
Tom
Mike
Mike

Source: codechef | Difficulty: HARD
Tags: Number theory

Game theory

Mathematics


Solutions:
def div(x):
	if x == 16 or x == 34 or x == 289:
		return 'Tom'
	elif x == 17 or x & 1 == 0:
		return 'Mike'
	else:
		t = int(x ** 0.5)
		for i in range(3, t + 1, 2):
			if x % i == 0:
				return 'Mike'
		return 'Tom'
for v in range(int(input())):
	x = int(input())
	print(div(x))


for i in range(int(input())):
	n = int(input())
	if n == 2 or n == 17:
		print('Mike')
	elif n == 16 or n == 34 or n == 289:
		print('Tom')
	elif n % 2 == 0:
		print('Mike')
	else:
		x = int(n ** 0.5)
		flag = False
		for i in range(3, x + 1, 2):
			if n % i == 0:
				print('Mike')
				flag = True
				break
		if not flag:
			print('Tom')


def solve(n):
	if n == 16 or n == 34 or n == 289:
		return 'Tom'
	if n == 17:
		return 'Mike'
	else:
		if n % 2 == 0:
			return 'Mike'
		tmp = int(n ** 0.5)
		for i in range(3, tmp + 1, 2):
			if n % i == 0:
				return 'Mike'
		return 'Tom'
t = int(input())
for i in range(t):
	n = int(input())
	print(solve(n))