**Kitty and Katty

Kitty and Katty

Kitty and Katty have N$N$ plastic blocks. They label the blocks with sequential numbers from 1$1$to N$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$2$ blocks, A$A$ and B$B$, from the set. They calculate A−B$A-B$, write the result on a new block, and insert the new block into the set.
• The game ends when only 1$1$ block is left. The winner is determined by the value written on the final block, X$X$:
  • If X%3=1$X\mathrm{\%}3=1$, then Kitty wins.
  • If X%3=2$X\mathrm{\%}3=2$, then Katty wins.
  • If X%3=0$X\mathrm{\%}3=0$, then the player who moved last wins.

Recall that %$\mathrm{\%}$ is the Modulo Operation.

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

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

Input Format

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

Constraints

• 1≤T≤100$1\le T\le 100$
• 1≤N≤105$1\le N\le {10}^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$N=2$ so there are two blocks labeled 1$1$ and 2$2$. Kitty chooses A=2$A=2$ and B=1$B=1$, then inserts a new block with the label 1$1$ (the result of 2−1$2-1$). The game ends, as there is now only 1$1$ block in the set. The label on the last block, X$X$, is 1$1$, so we calculate result=1 % 3=1$result=1\mathrm{\%}3=1$. Becauseresult=1$result=1$, Kitty wins and we print Kitty on a new line.

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

---------------------------------------editorial------------------------------------

Special Case

Let us first deal with the special case. When `N=1$N=1$`, there is only one element in the array, and nobody can make a move. Kitty wins since the remainder is `1$1$`.

Solution

For any arbitary `N>1$N>1$`, imagine the game is being played. Eventually, the game will come to a situation when there are exactly two elements in the array, `A$A$` and `B$B$`. Since the game is decided by the final value modulo `3$3$`, we can say that `a=A%3$a=A\mathrm{\%}3$` and `b=B%3$b=B\mathrm{\%}3$` and play with these two numbers instead. It will not affect the game state.

Now, if `a=b$a=b$`, then this player can simply replace `a,b$a,b$` with `a−b=0$a-b=0$`. The final value will be `0$0$`, and this player will win.

If they are not equal, then this player will still win. This player wins because she can choose the value of her move where either `1$1$` or `2$2$` is left as the final value.

Suppose `a=1$a=1$` and `b=2$b=2$`. If this player wants to have the final value as `1$1$`, then she will just choose `2$2$` and `1$1$` and replace them with `2−1=1$2-1=1$`. If she wants `2$2$`, then she will chose `1$1$` and `2$2$` and replace them with `1−2=−1$1-2=-1$`.

So, the player who makes the last move always wins. If `N$N$` is even, then Kitty wins, otherwise Katty wins.

-------------------------------------------------code--------------------------------------------

#include<bits/stdc++.h>

using namespace std;

int main(){

    int T;

    cin >> T;

    for(int a0 = 0; a0 < T; a0++){

        int n;

        cin >> n;

        if(n==1) cout<<"Kitty"<<endl;

        else if(n%2==0) cout<<"Kitty"<<endl;

        else cout<<"Katty"<<endl;

    }

    return 0;

}