All Submissions


There are 'N' piles of stones where the ith pile has 'xi' stones in it. Kanhaiya and Nitish play the following game:
  • Kanhaiya starts, and they alternate turns.
  • In a turn, a player can choose any one of the piles of stones and divide the stones in it into any number of unequal piles such that no two of the piles you create should have the same number of stones. For example, if there 8 stones in a pile, it can be divided into one of these set of piles: (1,2,5), (1,3,4), (1,7), (2,6) or (3,5).
  • The player who cannot make a move (because all the remaining piles are indivisible) loses the game.

Given the starting set of piles, who wins the game assuming both players play optimally?

Input

The first line contains the number of test cases T. T test cases follow. The first line for each test case contains N, the number of piles initially. The next line contains N space delimited numbers, the number of stones in each of the piles.

Output

Output T lines, one corresponding to each test case containing "KANHAIYA" if Kanhaiya wins the game and "NITISH" otherwise.

Constraints

1 <= T <= 50
1 <= N <= 50
1 <= xi <= 50

Sample Input


6
1
4
2
1 2
3
1 3 4
1
8
1
5
7
26 48 10 28 39 40 25


Sample Output


NITISH
NITISH
KANHAIYA
NITISH
KANHAIYA
KANHAIYA


Explanation

For the first case, the only possible move for Kanhaiya is (4) -> (1,3). Now Nitish breaks up the pile with 3 stones into (1,2). At this point Kanhaiya cannot make any move and has lost.

Problem Setter: Rounak Tibrewal

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0