Bituś i Bajtuś spędzają wakacje nad Morzem Bajtockim. Ale nawet na plaży, bardziej niż ciepły piasek i wysokie fale, interesują ich intelektualne rozrywki. Zgromadzili spory stosik okrągłych kamyków, które morze wyrzuciło na brzeg, i rozpoczęli nową grę. Zasady są bardzo proste. Bituś w pierwszym ruchu może zabrać dowolną niezerową liczbę kamyków, pod warunkiem że nie zabierze wszystkich. Następnie chłopcy (zaczynając od Bajtusia) wykonują naprzemiennie ruchy, a w każdym ruchu mogą zabrać taką niezerową liczbę kamyków (włączając w to zabranie całego stosiku), jaka nie była zabrana w żadnym poprzednim ruchu. Innymi słowy, w każdym ruchu należy zabrać inną liczbę kamyków. Przegrywa ten, kto nie może wykonać ruchu.

Mając daną liczbę kamyków na początku gry i zakładając, że obaj chłopcy grają optymalnie, sprawdź, czy grę wygra Bituś.

Input Format

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $ t $ ($1 \le t \le 1\,000\,000$), oznaczająca liczbę przypadków testowych do rozważenia.

W każdym z kolejnych $ t $ wierszy znajduje się po jednej liczbie całkowitej $ n $ ($1 \le n \le 1\,000\,000\,000$), która oznacza liczbę kamyków na początku gry.

Output Format

Na wyjście należy wypisać dokładnie $ t $ wierszy zawierających odpowiedzi dla kolejnych przypadków testowych z wejścia. Każdy wiersz powinien zawierać słowo TAK lub NIE, w zależności od tego, czy Bituś wygra grę.

Example

Input

1
3

Output

NIE