Stone Game

Memory limit: 128 MB

Bitie and Bytie are spending their vacation at the Bytic Sea. The boys really enjoy intellectual riddles, even when they are at the beach.

This time they gathered a number of round stones that were washed ashore and started playing a new game. The rules of the game are fairly simple. In the first move Bitie can take any number of stones that is greater than zero but smaller than the total number of stones in the heap. Since then the boys alternate moves, starting from Bytie. In each move a player can take any non-zero number of stones from the heap (possibly even all the stones from the heap) provided that this number of stones was not taken in any previous move. In other words, in each move a different number of stones must be taken. The player who cannot make a move loses.

Given the number of stones in the initial heap, your task is to check if Bitie can win the game assuming that both boys play optimally.

Input

The first line of input contains one integer (), the number of test cases.

Each of the following lines contains one integer (), the number of stones at the beginning of the game.

Output

Your program should output lines with answers to the respective test cases. Each line should contain the word TAK (Polish for yes) or NIE (Polish for no) depending on whether Bitie can win the game.

Example

For the input data:

1
3

the correct result is:

NIE