Bituś and Bajtuś are spending their vacation at the Byte Sea. However, even on the beach, they are more interested in intellectual entertainment than warm sand and high waves. They have gathered a large pile of round pebbles washed ashore by the sea and started a new game. The rules are very simple. In the first move, Bituś can take any non-zero number of pebbles, provided he does not take all of them. Then, the boys (starting with Bajtuś) take turns, and in each move, they can take a non-zero number of pebbles (including taking the entire remaining pile) that has not been taken in any previous move. In other words, each move must involve taking a different number of pebbles. The player who cannot make a move loses.

Given the number of pebbles at the beginning of the game and assuming both boys play optimally, determine if Bituś will win the game.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 1\,000\,000$), representing the number of test cases to consider.

Each of the following $t$ lines contains a single integer $n$ ($1 \le n \le 1\,000\,000\,000$), which represents the number of pebbles at the beginning of the game.

Output

Output exactly $t$ lines containing the answers for the consecutive test cases from the input. Each line should contain the word TAK or NIE, depending on whether Bituś wins the game.

Examples

Input 1

1
3

Output 1

NIE