10012번 - Kamyki 다국어

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ś.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita t (1 ≤ t ≤ 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 ≤ n ≤ 1 000 000 000), która oznacza liczbę kamyków na początku gry.

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ę.