Beer Numbers

During a night out at a pub, a group of computer scientists decided to keep count of how many mugs of beer they had drunk. Leaving an empty mug on the table after every beer quickly caused trouble with space and with passing the next round around. After a short discussion they switched to binary, using the two possible ways a mug can stand on the table, ⊔ and ⊓, as the two binary digits. This cut down the number of mugs needed to record a number.

A new problem appeared, though. Because of the noise and the heated debate, whoever was recording the count often forgot which of the two mug positions they had chosen to mean the digit 1. On top of that, they sometimes could not remember whether the number had been laid out from left to right or from right to left.

After thinking it over they noticed that some counts can still be reconstructed unambiguously from the row of mugs alone, even without knowing these two facts. The computer scientists called such numbers beer numbers. Help them decide which numbers are beer numbers!

More precisely: write a positive integer $n$ in binary (with no leading zero) and lay it out with mugs. The number $n$ is a beer number if $n$ itself is the only integer that produces the very same row of mugs under some choice of which position means 1 and some reading direction.

The first line contains a small integer $z$, the number of data sets that follow one after another.

Each data set consists of a single integer $n$ with $1 \le n \le 10^{1000}$.

For each data set, print TAK if the given number is a beer number, and NIE otherwise, one answer per line.