We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 6
  3. Kitty and Katty

Kitty and Katty

Kitty and Katty have plastic blocks. They label the blocks with sequential numbers from to 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 blocks, and , from the set. They calculate , write the result on a new block, and insert the new block into the set.
  • The game ends when only block is left. The winner is determined by the value written on the final block, :
    • If , then Kitty wins.
    • If , then Katty wins.
    • If , then the player who moved last wins.

Recall that is the Modulo Operation.

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

Note: The selection order for and matters, as sometimes . The diagram below shows an initial set of blocks where . If and , then the newly inserted block is labeled ; alternatively, if and , the newly inserted block is labeled .

Input Format

The first line contains a single positive integer, (the number of test cases or games).
The subsequent lines each contain an integer, (the number of blocks for that test case).

Constraints


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:
so there are two blocks labeled and . Kitty chooses and , then inserts a new block with the label (the result of ). The game ends, as there is now only block in the set. The label on the last block, , is , so we calculate . Because , Kitty wins and we print Kitty on a new line.

Test Case 1:
, so there are three blocks labeled , , and . No matter how Kitty makes the first move, Katty will win. If Kitty chooses and on the first move and inserts a block labeled (the result of ), the set of blocks becomes . Katty then must choose and and insert a new block labeled (the result of ). The game ends, as there is now only block in the set. The label on the last block, , is , so we calculate . Because and Katty made the last move, Katty wins and we print Katty on a new line.