Problem description

Jasio, jak każdy normalny chłopiec w jego wieku, ma swój ulubiony zbiór X. Spełnia on następujące własności:

• 1 ∈ X,
• jeżeli a ∈ X to również 2a + 1 ∈ X,
• jeżeli a ∈ X to również 3a ∈ X,
• jeżeli a ∈ X to również 5a ∈ X,
• do zbioru X nie należą żadne inne liczby, których nie można uzyskać regułami opisanymi powyżej.

Trochę enigmatyczna ta definicja ulubionego zbioru Jasia, prawda? Wypadałoby to jakoś rozszyfrować, na przykład tak, żeby być w stanie szybko stwierdzać jakie liczby należą do tego zbioru, a jakie nie. Czy podołasz temu zadaniu?

Napisz program, który: wczyta ciąg liczb naturalnych, dla każdej z nich stwierdzi czy należy do zbioru X i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z jednej liczby naturalnej A_i.

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 zapytania. Odpowiedź dla każdego zapytania to jedno słowo TAK lub NIE w zależności od tego czy liczba A_i należy do zbioru X czy nie.

Ograniczenia

1 ≤ Q ≤ 10 000, 1 ≤ A_i ≤ 10¹⁸.

Przykład

3
3
2
15

TAK
NIE
TAK