Problem description

Jasio uwielbia grę Nim. Co chwilę wymyśla nowe warianty tej gry. Tym razem udało mu się stworzyć jakiś nietrywialny. Na tyle trudny, że nie potrafi opracować strategii wygrywającej nawet w grze na jeden stosik! Grę postanowił nazwać nimopodobną.

Gra nimopodobna to gra dla dwóch graczy, która odbywa się z użyciem stosu N kamieni. Gracze, wykonując naprzemienne ruchy, w każdym z nich mogą wykonać jedną z dwóch czynności:

• zdjąć jeden kamień (z niepustego stosu),

• zdjąć połowę liczby kamieni ze stosu (z niepustego stosu), jeśli liczba kamieni na stosie była nieparzysta, należy zaokrąglić ją w górę.

Na przykład: jeśli na stosie jest 5 kamieni to gracz może albo zabrać jeden kamień (pozostawiając na stosie 4 kamienie), albo zabrać 3 kamienie (pozostawiając na stosie 2 kamienie). Gra kończy się, gdy nie można już wykonać ruchu (gdy kamienie się skończą). Gracz, którego wtedy kolej (i nie może wykonać ruchu) przegrywa.

Mówimy, że gracz ma strategię wygrywającą jeśli może wygrać grę niezależnie od ruchów przeciwnika (przy założeniu, że sam będzie grał optymalnie).

Napisz program, który: wczyta liczbę kamieni na stosie N, wyznaczy czy gracz rozpoczynający grę ma strategię wygrywającą i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zestawów danych. W kolejnych Q wierszach znajdują się opisy kolejnych zestawów danych. Opis każdego zestawu danych składa się z jednej liczby naturalnej N, określającej początkową liczbę kamieni w grze.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym z nich powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego zestawu danych to jedno słowo TAK, jesli gracz rozpoczynający ma strategię wygrywającą lub NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ Q ≤ 15, 1 ≤ N ≤ 10¹⁸.

Przykład

3
4
7
8

TAK
TAK
NIE