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.
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.
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.
For the input data:
1 3
the correct result is:
NIE
W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem szkopul@fri.edu.pl.
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, odwiedź nasze serwery na Discordzie. Są one moderowane przez społeczność, ale członkowie zespołu wsparcia również aktywnie się tam udzielają.