Problem description

Alicja i Bob grają w następującą grę: Na stole leży N kamieni. W każdym ruchu wolno ze stosu zabrać pewną liczbę kamieni, o ile jest to liczba pierwsza. Alicja zawsze zaczyna. Potem ruchy wykonują na przemian. Gracz, który nie może wykonać ruchu (bo zostało zbyt mało kamieni), przegrywa.

Mówimy, że gracz ma strategię wygrywającą, jeśli jest w stanie wygrać niezależnie od ruchów przeciwnika. Alicja zastanawia się dla jakich N posiada strategię wygrywającą. Pomóż jej!

Napisz program, który: wczyta wiele zestawów danych dotyczących różnych gier, dla każdej z gier określi czy Alicja ma w niej strategię wygrywającą i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zestawów danych. W kolejnych Q wierszach znajduje się opis kolejnych zestawów danych. Opis każdego zestawu danych składa się z jednej liczby naturalnej N_i, określającej początkowy rozmiar stosu w i-tej grze.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź powinna być TAK, jeśli Alicja ma strategię wygrywającą w i-tej grze, zaś NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ Q ≤ 10 000, 1 ≤ N_i ≤ 50 000.

Przykład

1
6

TAK