tic-tac-toe-numbers-3
Source: hackerearth
Difficulty: EASY

Tic-Tac-Toe are three cousins. They are playing a game on Fibonacci numbers. The rule of the game is simple -
If the sum of Non-Fibonacci numbers upto N is prime, Tic wins.
If the sum of Non-Fibonacci numbers upto N is even, Tac wins.
If the sum of Non-Fibonacci numbers upto N is odd and not prime, Toe wins.

Fibonacci Numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21 . . . . .

Input: First line of the input contains T, followed by T lines, each containing a number N.

Output: T lines, each containing winners name (Tic, Tac or Toe).

Constraints: 1 ≤ T ≤ 100 | N ≤ 10 ^ 6

SAMPLE INPUT
5
91
12
135
7
66

SAMPLE OUTPUT
Tac
Tic
Tac
Tac
Tic

Explanation

For the 2nd case, N = 12
Fibonacci series till N -> {0,1,1,2,3,5,8}
Sum of Non-Fibonacci numbers upto 12 is -> 4 + 6 + 7 + 9 + 10 + 11 = 47, which is a prime number.
So, Tic wins.


fibarr=[0]
i=1
temp=0
while i<=1000000:
	temp=temp+i
	b=temp
	temp=i
	i=b
	fibarr.append(temp)
#print fibarr
for _ in range(eval(input())):
	a=eval(input())
	
	add=0
	for item in range(4,a):
		if item not in fibarr:
			add=add+item
	
	if add%2==0:
		print("Tac")
	else:
		for divide in range(2,int(add**0.5+1)):
			if add%divide==0:
				print("Toe")
				break
		else:
			print("Tic")


import math
t=eval(input())
sum1 =0;
l=[]
l1=[]
while t!=0:
	n=eval(input())
	a,b=1,1
	for i in range(n-1):
			a,b= b,a+b
			if a<n:
			   l.append(a)
			else:
				break
			
	for i in range(0,n):
		if i not in l:
			l1.append(i)
	sum1=sum(l1)
	for i in range(2,int(math.sqrt(sum1))):
		if sum1%i==0:
			flag=0
			break
		else:
			flag=1
	if(flag==1):
	    print("Tic")
	elif(sum1%2==0):
	    print("Tac")
	else:
	    print("Toe")

	l=[]
	l1=[]
	t=t-1      


def isprime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	sqrt = int(num**0.5)
	for i in range(2, sqrt):
		if num % i == 0:
			return False
	return True


def fibo(val):
	a, b = 1, 2
	
	while a < val:
		yield a
		a, b = b, a+b


testcases = eval(input())
for testcase in range(testcases):
	num = eval(input())
	add = 0
	for i in fibo(num):
		add += i
	real_add = num*(num-1)//2 - add

	if isprime(real_add):
		print("Tic")
	elif real_add % 2 == 0:
		print("Tac")
	elif real_add % 2 != 0:
		print("Toe")


from math import sqrt

fib = [0, 1, 2]
for i in range(3, 36):
	fib.append(fib[i - 1] + fib[i - 2])

is_prime = [False for _ in range(0, int(1e6) + 30)]
prime = [2]
for i in range(3, int(1e6) + 7, 2):
	if not is_prime[i]:
		prime.append(i)
		for j in range(i + i, int(1e6) + 7, i):
			is_prime[j] = True


T = int(input())
for _ in range(T):
	N = int(input())
	cur, idx = 0, 0
	while fib[idx] <= N:
		cur += fib[idx]
		idx += 1
	res = (N * (N - 1)) / 2 - cur

	if res % 2 == 1:
		flag = True
		cur, idx = prime[0], 0
		while cur < int(sqrt(res)) + 1:
			if res % cur == 0:
				print('Toe')
				flag = False
				break
			idx += 1
			cur = prime[idx]
		if flag:
			print('Tic')
	else:
		print('Tac')



from math import sqrt

def isprime(n):
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

n = int(input())
arr = []

for i in range(n):
	no = int(input())
	arr.append(no)

no = max(arr)

fib = [0, 1]

while fib[-1] < no:
	fib.append(fib[-1] + fib[-2])

for n in arr:
	s = 0
	for i in range(1, n):
		if i not in fib:
			s = s + i
	if isprime(s):
		print('Tic')
	elif s % 2 == 0:
		print('Tac')
	else:
		print('Toe')
	




def prime(n):
	if(n==1 or n==0):
		return 1
	import math
	i=2
	while(i<int(math.sqrt(n))):
		if(n%i==0):
			return 0
		i=i+1
	return 1





tests=eval(input())
while(tests>0):
	n=eval(input())
	sum=(n-1)*(n)
	sum=sum/2
	a=0
	b=1
	c=1
	while(c<n):
		sum=sum-c
		c=a+b
		a=b
		b=c
	if((sum+1)%2==0):
		print("Tac")
	elif(prime(sum+1)==1):
		print("Tic")
	else:
		print("Toe")
	
	tests=tests-1

	


fib = [1,1];
def genFib():
	lastOne =1;
	lastTwo =1;
	t =0;
	while(lastOne<=1000000):
		t = lastOne;
		lastOne =lastOne+lastTwo;
		lastTwo = t;
		fib.append(lastOne);
def isPrime(number):
	for x in range (2 , int(number**0.5) +1):
		if(number % x == 0):
			return False;
	return True;
genFib()
inputs =int(input());
for x in range (0 , inputs):
	sum =0;
	for i in range(4 ,int(input())):
		if(fib.count(i) == 0):
			sum = sum +i;
	if(sum %2 ==0):
		print('Tac');
	elif(isPrime(sum)):
		print('Tic')
	else:
		print('Toe')
		



fib = [1,1];
def genFib():
	lastOne =1;
	lastTwo =1;
	t =0;
	while(lastOne<=1000000):
		t = lastOne;
		lastOne =lastOne+lastTwo;
		lastTwo = t;
		fib.append(lastOne);
def isPrime(number):
	for x in range (2 , int(number**0.5) +1):
		if(number % x == 0):
			return False;
	return True;
genFib()
inputs =int(input());
for x in range (0 , inputs):
	sum =0;
	for i in range(4 ,int(input())):
		if(fib.count(i) == 0):
			sum = sum +i;
	if(sum %2 ==0):
		print('Tac');
	elif(isPrime(sum)):
		print('Tic')
	else:
		print('Toe')
		



def prime(n):
	if(n==1 or n==0):
		return 1
	import math
	i=2
	while(i<int(math.sqrt(n))):
		if(n%i==0):
			return 0
		i=i+1
	return 1





tests=eval(input())
while(tests>0):
	n=eval(input())
	sum=(n-1)*(n)
	sum=sum/2
	a=0
	b=1
	c=1
	while(c<n):
		sum=sum-c
		c=a+b
		a=b
		b=c
	if((sum+1)%2==0):
		print("Tac")
	elif(prime(sum+1)==1):
		print("Tic")
	else:
		print("Toe")
	
	tests=tests-1

	


n=eval(input())
s=[]
for i in range(0,n):
	s=s+[eval(input())]
	if i==0:
		large=s[0]
	else:
		if s[i]>large:
			large=s[i]
fib=[]
a=0
b=1
while b<=large:
	m=a+b
	a=b
	b=m
	fib=fib+[m]
for z in s:
	sum=0
	for y in range(4,z):
		if y not in fib:
			sum+=y
	if sum%2==0:
		print("Tac")
	else:
		n=0
		f=2
		while f<=(sum**0.5):
			if sum%f==0:
				n=1
				print("Toe")
				break
			else:
				f+=1
		if n==0:
			print("Tic")




fibarr=[0]
i=1
temp=0
while i<=1000000:
	temp=temp+i
	b=temp
	temp=i
	i=b
	fibarr.append(temp)
#print fibarr
for _ in range(eval(input())):
	a=eval(input())
	
	add=0
	for item in range(4,a):
		if item not in fibarr:
			add=add+item
	
	if add%2==0:
		print("Tac")
	else:
		for divide in range(2,int(add**0.5+1)):
			if add%divide==0:
				print("Toe")
				break
		else:
			print("Tic")