Pebbles

Bituś and Bajtuś are spending the holidays by the Byte Sea. Warm sand and tall waves interest them far less than a good puzzle, so they gathered a sizeable pile of round pebbles that the sea had washed ashore and started a new game.

The rules are simple. Bituś moves first. He must take at least one pebble, and he is not allowed to take the whole pile. After that the boys move alternately, starting with Bajtuś, and on each move a player may take at least one pebble, in an amount that was not taken on any earlier move. Taking everything that is left is allowed. In short, every move removes a different number of pebbles, and the amount Bituś took on the opening move already counts as used. A player who cannot take anything on their turn loses.

Given the number of pebbles at the start of the game, and assuming both boys play optimally, decide whether Bituś wins.

The first line contains one integer $t$ ($1 \le t \le 10^6$), the number of test cases.

Each of the next $t$ lines contains one integer $n$ ($1 \le n \le 10^9$), the number of pebbles at the start of that game.

Print exactly $t$ lines. The $i$-th line holds the answer for the $i$-th test case: TAK if Bituś wins the game, and NIE if he does not.