Kitty and Katty have $N$ plastic blocks. They label the blocks with sequential numbers from $\mbox{1}$ to $N$ and begin playing a game in turns, with Kitty always taking the first turn. The game's rules are as follows:

For each turn, the player removes $2$ blocks, $\mbox{A}$ and $\mbox{B}$, from the set. They calculate $A-B$, write the result on a new block, and insert the new block into the set. 
The game ends when only $\mbox{1}$ block is left. The winner is determined by the value written on the final block, $\mbox{X}$:
If $X\%3=1$, then Kitty wins.
If $X\%3=2$, then Katty wins.
If $X\%3=0$, then the player who moved last wins.

Recall that $\%$ is the Modulo Operation.

Given the value of $N$, can you find and print the name of the winner? Assume that both play optimally.

Note: The selection order for $\mbox{A}$ and $\mbox{B}$ matters, as sometimes $A-B\neq B-A$. The diagram below shows an initial set of blocks where $N=5$. If $A=2$ and $B=3$, then the newly inserted block is labeled $-1$; alternatively, if $A=3$ and $B=2$, the newly inserted block is labeled $\mbox{1}$.

Input Format

The first line contains a single positive integer, $\mathbf{T}$ (the number of test cases or games). 

The $\mathbf{T}$ subsequent lines each contain an integer, $N$ (the number of blocks for that test case).

Constraints 

$1\leq T\leq100$

$1\leq N\leq10^5$

Output Format

For each test case, print the name of the winner (i.e.: either Kitty or Katty) on a new line.

Sample Input
2
2
3

Sample Output
Kitty
Katty

Explanation

Test Case 0: 

$N=2$ so there are two blocks labeled $\mbox{1}$ and $2$. Kitty chooses $A=2$ and $B=1$, then inserts a new block with  the label $\mbox{1}$ (the result of $2-1$). The game ends, as there is now only $\mbox{I}$ block in the set. The label on the last block, $\mbox{X}$, is $\mbox{1}$, so we calculate $result=1\%3=1$. Because  $result=1$, Kitty wins and we print Kitty on a new line.

Test Case 1: 

$N=3$, so there are three blocks labeled $\mbox{1}$, $2$, and $3$. No matter how Kitty makes the first move, Katty will win. If Kitty chooses $A=3$ and $B=2$ on the first move and inserts a block labeled $\mbox{I}$ (the result of $3-2$), the set of blocks becomes $\{1,1\}$. Katty then must choose $A=1$ and $B=1$ and insert a new block labeled $\mbox{o}$ (the result of $1-1$). The game ends, as there is now only $\mbox{I}$ block in the set. The label on the last block, $\mbox{X}$, is $\mbox{0}$, so we calculate $result=0\%3=0$. Because $result=0$ and Katty made the last move, Katty wins and we print Katty on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1 or N % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


[[print(('Ki' if (n < 2) ^ (n % 2 < 1) else 'Ka') + 'tty') for n in [int(input())]] for x in [0] * int(input())]


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys

def main():
	t = int(input())
	for _ in range(t):
		n = int(input().strip())
		if n == 1:
			print('Kitty')
		elif n > 1:
			if n % 2 == 0:
				print('Kitty')
			else:
				print('Katty')
		else:
			print('Error!')
main()


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


def main():
	t = int(input())
	for _ in range(t):
		n = int(input().strip())
		if n == 1:
			print('Kitty')
		elif n > 1:
			if n % 2 == 0:
				print('Kitty')
			else:
				print('Katty')
		else:
			print('Error!')
main()


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
		continue
	if n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


for a0 in range(int(input())):
	n = int(input().strip())
	print('Kitty' if n == 1 or n % 2 == 0 else 'Katty')


import sys

def win(n):
	return not n % 2
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	print('Kitty' if win(n) or n == 1 else 'Katty')


T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


def choose_one(counts):
	for i in range(len(counts)):
		if counts[i]:
			yield (i, tuple((n - 1 if i == j else n for (j, n) in enumerate(counts))))

def moves(counts):
	for (a, temp_a) in choose_one(counts):
		for (b, temp_b) in choose_one(temp_a):
			i = (a - b) % len(counts)
			yield tuple((n + 1 if i == j else n for (j, n) in enumerate(temp_b)))

def who_wins(counts, whose_move, _cache={}):
	if (whose_move, counts) in _cache:
		return _cache[whose_move, counts]
	other = whose_move ^ 1
	if sum(counts) == 1:
		winner = (other, 0, 1)[counts.index(1)]
		_cache[whose_move, counts] = winner
		return winner
	for move in moves(counts):
		if who_wins(move, other, _cache) == whose_move:
			_cache[whose_move, counts] = whose_move
			return whose_move
	_cache[whose_move, counts] = other
	return other

def main():
	for _ in range(int(input())):
		n = int(input())
		print('Kitty' if n == 1 else ('Kitty', 'Katty')[n & 1])
main()


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


T = int(input())
for _ in range(T):
	n = int(input())
	if n == 1 or n & 1 == 0:
		print('Kitty')
	else:
		print('Katty')


T = int(input())
for Ca in range(T):
	n = int(input())
	if n % 2 and n != 1:
		print('Katty')
	else:
		print('Kitty')


for _ in range(int(input())):
	x = int(input())
	print('Katty' if x > 1 and x % 2 else 'Kitty')


import sys

def solution(n):
	if n == 1:
		return 'Kitty'
	if n % 2 == 1:
		return 'Katty'
	else:
		return 'Kitty'
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	print(solution(n))


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n >= 2:
		if n % 2 == 1:
			print('Katty')
		else:
			print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		if n % 3 == 2:
			print('Katty')
		else:
			print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


for _ in range(int(input())):
	n = int(input())
	if n == 1 or n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	else:
		print(['Kitty', 'Katty'][n % 2])


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 2 and n != 1:
		print('Katty')
	else:
		print('Kitty')


T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1 or N % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
D = {}

def A(x, n):
	global D
	if (x, n) not in D.keys():
		if sum(x) == 1:
			if x[0] == 1:
				D[x, n] = 'p'
			elif x[1] == 1:
				if n == 0:
					D[x, n] = 'p'
				else:
					D[x, n] = 'n'
			elif n == 0:
				D[x, n] = 'n'
			else:
				D[x, n] = 'p'
		else:
			qui = 1
			for k in range(0, 3):
				if x[k] >= 2:
					b = list(x)
					b[k] -= 2
					b[0] += 1
					if A(tuple(b), n) == 'p':
						qui = 0
						D[x, n] = 'n'
						break
				if x[k] != 0:
					for kk in range(k + 1, 3):
						if x[kk] != 0:
							b = list(x)
							b[(k - kk) % 3] += 1
							b[k] -= 1
							b[kk] -= 1
							if A(tuple(b), n) == 'p':
								qui = 0
								D[x, n] = 'n'
								break
							b[(k - kk) % 3] -= 1
							b[(kk - k) % 3] += 1
							if A(tuple(b), n) == 'p':
								qui = 0
								D[x, n] = 'n'
								break
				if qui == 0:
					break
			else:
				D[x, n] = 'p'
	return D[x, n]
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n is 1:
		print('Kitty')
	elif n % 2 is 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import sys

def find_winner(n):
	group = []
	for i in range(n):
		group.append(i + 1)
	for i in range(n - 1):
		x = group.pop()
		y = group.pop()
		group.append(x - y)
	ans = group[0] % 3
	if n % 2 == 0 or n == 1:
		winner = 'Kitty'
	else:
		winner = 'Katty'
	return winner
group = []
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	print(find_winner(n))


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 2 == 1 and n != 1:
		print('Katty')
	else:
		print('Kitty')


def parseInput(f):
	return [f(x) for x in input().split()]
t = int(input())
for _ in range(t):
	n = int(input())
	print('Kitty' if n == 1 or n % 2 == 0 else 'Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	elif n & 1:
		print('Katty')
	else:
		print('Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


import sys

def nim_sum(n):
	nim = 0
	for i in range(n):
		nim ^= i
	return nim

def recur(n, n_block, kitty=True):
	if n == 1:
		goal = n_block[0] % 3
		if goal == 0:
			return not kitty
		elif goal == 1:
			return True
		else:
			return False
	for i in range(n):
		for j in range(n):
			new_b = [n_block[g] for g in range(n) if g not in [i, j]]
			new_b.append(n_block[i] - n_block[j])
			state = recur(n - 1, new_b, not kitty)
			if kitty and state:
				return True
			elif not kitty and (not state):
				return False
	return not kitty
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
	else:
		print('Kitty' if n % 2 == 0 else 'Katty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	print('Katty' if n % 2 == 1 and n > 2 else 'Kitty')


for _ in range(int(input())):
	n = int(input())
	print('Katty' if n != 1 and n & 1 else 'Kitty')


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	if n == 1:
		print('Kitty')
		continue
	if n % 2 == 1:
		print('Katty')
	else:
		print('Kitty')


import sys
from time import time
wcache = dict()

def win(c0, c1, c2):
	t = (c0, c1, c2)
	if t in wcache:
		return wcache[t]
	if t == (1, 0, 0):
		rval = False
	elif t == (0, 1, 0):
		rval = True
	elif t == (0, 0, 1):
		rval = False
	else:
		rval = False
		if c0 > 1 and (not win(c0 - 1, c1, c2)):
			rval = True
		elif c1 > 1 and (not win(c0 + 1, c1 - 2, c2)):
			rval = True
		elif c2 > 1 and (not win(c0 + 1, c1, c2 - 2)):
			rval = True
		elif c0 and c1 and (not win(c0 - 1, c1, c2) or not win(c0 - 1, c1 - 1, c2 + 1)):
			rval = True
		elif c1 and c2 and (not win(c0, c1, c2 - 1) or not win(c0, c1 - 1, c2)):
			rval = True
		elif c0 and c2 and (not win(c0 - 1, c1 + 1, c2 - 1) or not win(c0 - 1, c1, c2)):
			rval = True
	wcache[t] = rval
	print('\t\tt=%s rval=%s' % (t, rval), file=sys.stderr)
	return rval

def solve(n):
	print('n=%d' % n, file=sys.stderr)
	c0 = c1 = c2 = n // 3
	r = n % 3
	if r == 1:
		c1 += 1
	elif r == 2:
		c1 += 1
		c2 += 1
	print('\tc0=%d c1=%d c2=%d' % (c0, c1, c2), file=sys.stderr)
	if n == 1:
		return True
	return n % 2 == 0
tm = time()
t = int(input())
for _ in range(t):
	n = int(input())
	if solve(n):
		print('Kitty')
	else:
		print('Katty')
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	i = 2
	ans = 1
	while i <= n:
		ans = abs(ans - i)
		i += 1
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n < 3:
		print('Kitty')
	elif n % 2 == 1:
		print('Katty')
	else:
		print('Kitty')


import math
import os
import random
import re
import sys

def other(player):
	return 1 if player == 2 else 2

def playerName(player):
	return 'Kitty' if player == 1 else 'Katty'

def optimalPlayWinner(blocks, player):
	if len(blocks) == 2:
		if (blocks[0] - blocks[1]) % 3 == player:
			return player
		if (blocks[1] - blocks[0]) % 3 == player:
			return player
		if (blocks[0] - blocks[1]) % 3 == 0:
			return player
		if (blocks[1] - blocks[0]) % 3 == 0:
			return player
		return other(player)
	for ai in range(0, len(blocks)):
		for bi in range(0, len(blocks)):
			if ai == bi:
				continue
			newBlocks = list(blocks)
			newBlock = blocks[ai] - blocks[bi]
			del newBlocks[ai]
			del newBlocks[bi - (1 if ai < bi else 0)]
			newBlocks.append(newBlock)
			winner = optimalPlayWinner(newBlocks, other(player))
			if winner == player:
				return player
	return other(player)

def winner(n):
	if n == 1:
		return playerName(1)
	return playerName(n % 2 + 1)
T = int(input())
for T_itr in range(T):
	n = int(input())
	print(winner(n))


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


T = int(input())
for t in range(T):
	N = int(input())
	print('Katty' if N != 1 and N & 1 else 'Kitty')


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n % 2 == 0:
		print('Kitty')
	elif n == 1:
		print('Kitty')
	else:
		print('Katty')


for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1 or n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys

def project():
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')
T = int(input())
for T_itr in range(T):
	n = int(input())
	project()


for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	print('Kitty' if n == 1 or n % 2 == 0 else 'Katty')


import math
import os
import random
import re
import sys

def g(n):
	if n == 1:
		return 'Kitty'
	elif n % 2 == 0:
		return 'Kitty'
	else:
		return 'Katty'
T = int(input())
er = []
for T_itr in range(T):
	n = int(input())
	er.append(n)
for item in er:
	print(g(item))


for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1 or not n & 1:
		print('Kitty')
	else:
		print('Katty')


for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	print('Kitty' if n == 1 or n % 2 == 0 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	print('Kitty' if n % 2 == 0 or n == 1 else 'Katty')


import math
import os
import random
import re
import sys

def winner(n):
	return 'Kitty' if n == 1 or n % 2 == 0 else 'Katty'
T = int(input())
for T_itr in range(T):
	n = int(input())
	print(winner(n))


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1 or not n & 1:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1 or not n & 1:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1 or n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1 or n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


import math
import os
import random
import re
import sys

def game(n):
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')
T = int(input())
for T_itr in range(T):
	n = int(input())
	game(n)


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')


for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
LastPerson = ''
A = 0
B = 0
R = 0
x = []
for T_itr in range(T):
	n = int(input())
	if n % 2 == 0 or n == 1:
		LastPerson = 'Kitty'
	else:
		LastPerson = 'Katty'
	print(LastPerson)


import math
import os
import random
import re
import sys
for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
for n in (int(input()) for _ in range(int(input()))):
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys

def gamestart(n):
	if n == 1 or n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')
T = int(input())
for T_itr in range(T):
	n = int(input())
	gamestart(n)


import math
import os
import random
import re
import sys

def get_winner(n):
	if n % 2 == 0 or n == 1:
		print('Kitty')
	else:
		print('Katty')
T = int(input())
for T_itr in range(T):
	n = int(input())
	get_winner(n)


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


for _ in range(int(input())):
	n = int(input())
	print('Kitty' if n == 1 or not n & 1 else 'Katty')


import math
import os
import random
import re
import sys
T = int(input())
for T_itr in range(T):
	n = int(input())
	if n == 1:
		print('Kitty')
	elif n % 2 == 0:
		print('Kitty')
	else:
		print('Katty')


T = int(input())
for N in range(T):
	N = int(input())
	if N == 1:
		print('Kitty')
	elif N % 2 == 0:
		print('Kitty')
	else:
		print('Katty')