Wstęp do programowania w C++

Liczby szczęśliwe

Co to są i jak powstają liczby szczęśliwe?
Wypiszmy kolejne liczby naturalne zaczynając od liczby 1, po czym usuńmy co drugą (wszystkie parzyste). Pozostanie ciąg liczb nieparzystych: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ... Z tego ciągu usuńmy teraz co trzecią liczbę. Co trzecią nie dlatego, że jest po dwójce, ale dlatego, że była ona drugą liczbą w ciągu, który powstał po pierwszej operacji. Otrzymujemy ciąg: 1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, ... Dalej popatrzmy, jaka jest trzecia liczba w nowo utworzonym ciągu. Siódemka. Usuwamy więc teraz co siódmą liczbę z tego ciągu. Pierwszą usuniętą liczbą będzie 19. Z nowego ciągu będziemy usuwać co dziewiątą liczbę, bo na czwartej pozycji została nam dziewiątka. Teraz jako pierwsza zostanie usunięta liczba 27, bo była ona na pozycji dziewiątej. W piątym kroku będziemy usuwać co trzynastą liczbę, w szóstym co piętnastą, i tak dalej, w nieskończoność. Liczby, które zostaną zdefiniujemy jako liczby szczęśliwe.

No to teraz trzeba postawić jakiś problem. Twoim zadaniem, a właściwie zadaniem twojego programu, będzie rozstrzygnąć, czy podana liczba na wejściu jest szczęśliwa.

Wejście
W pierwszym wierszu wejścia znajduje się liczba zapytań q (1 ≤ q ≤ 1000). Każde zapytanie to jedna liczba naturalna n (1≤n≤ 10⁶), każda liczba w osobnym wierszu.

Wyjście
Dla każdego zapytania w osobnym wierszu należy wypisać słowo TAK, jeśli sprawdzana liczba jest szczęśliwa, albo słowo NIE w przeciwnym przypadku.

Przykład

Wejście
2
2018
2019

Wyjście
NIE
TAK