조약돌 게임

비투시와 바이투시는 바이트해 바닷가에서 방학을 보내고 있다. 따뜻한 모래나 높은 파도보다 머리 쓰는 놀이가 훨씬 재미있는 둘은, 바다가 밀어 올린 동그란 조약돌을 한 무더기 모아 놓고 새 게임을 시작했다.

규칙은 간단하다. 첫 수는 비투시가 둔다. 비투시는 조약돌을 1개 이상 가져가야 하지만 무더기 전체를 가져갈 수는 없다. 그다음부터는 바이투시부터 시작해 번갈아 수를 두며, 각자 자기 차례에 1개 이상이면서 앞선 어떤 수에서도 가져간 적 없는 개수만큼 조약돌을 가져갈 수 있다. 남은 무더기를 통째로 가져가도 된다. 즉 매 수마다 가져가는 개수가 모두 달라야 한다. 첫 수에서 비투시가 가져간 개수도 이미 쓴 개수로 친다. 자기 차례에 아무것도 가져갈 수 없는 사람이 진다.

게임을 시작할 때의 조약돌 개수가 주어진다. 두 사람이 모두 최선으로 둔다고 할 때, 비투시가 이기는지 판정하시오.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^6$)가 주어진다.

이어지는 $t$개의 줄에 정수 $n$ ($1 \le n \le 10^9$)이 한 줄에 하나씩 주어진다. $n$은 그 게임을 시작할 때의 조약돌 개수이다.

$t$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트 케이스의 답을 출력하는데, 비투시가 이기면 TAK을, 지면 NIE를 출력한다.