Podczas pewnej wizyty w pubie, grupa informatyków postanowiła liczyć wypite kufle piwa. Szybko okazało się, że zostawianie na stole pustego kufla po każdym piwie powoduje kłopoty z ilością miejsca i dalszą dystrybucją napoju. Po krótkim namyśle zgromadzeni postanowili przejść na zapis binarny wykorzystując dwa możliwe ustawienia kufla na stole: ⊔,⊓. Taka metoda spowodowała znaczne zmniejszenie liczby kufli zużywanych do zapisu. Pojawił się jednak nowy problem. Osoba zapisująca liczbę wypitych piw z uwagi na gwar rozmów i gorącą atmosferę dyskusji bardzo często zapominała, którym ustawieniem kufla oznaczała 1 z zapisu binarnego. Ponadto zdarzało się również zapomnieć, czy liczba została zapisana na stole od prawej do lewej czy od lewej do prawej... Po krótkim zastanowieniu stwierdzono jednak, że niektóre liczby wypitych piw po zapisaniu kuflami dają się jednoznacznie odtworzyć nawet z pominięciem tych dwóch informacji. Informatycy nazwali je liczbami piwnymi. Pomóż im ustalić jakie liczby jest bezpiecznie ustawiać z kufli!

입력 형식

Pierwsza linia wejścia zawiera małą liczbę całkowitą z – liczbę zestawów danych występujących kolejno po sobie. Opis jednego zestawu jest następujący:</p>

Składa się on z jednej liczby całkowitej n (1 ≤ n ≤ 10¹⁰⁰⁰).

출력 형식

Dla każdego zestawu danych wypisz TAK jeśli liczba podana w zestawie jest piwna, w przeciwnym wypadku wypisz NIE.

예제 입력

3
1
4
7

예제 출력

TAK
NIE
TAK