Wstęp do programowania w C++

W małej wiosce o nazwie "Fraktalocja" mieszkała Wiktoria, utalentowana programistka, który zawsze była zafascynowana liczbami i matematyką. Pewnego dnia postanowiła stworzyć program, który sprawdzi, czy dana liczba może być przedstawiona jako suma różnych wartości silni.

Wiktoria wiedziała, że silnia z liczby n to iloczyn wszystkich dodatnich liczb całkowitych od 1 do n. Chciała, aby jej program pomógł ludziom z "FRAKTALOCJI" dowiedzieć się, czy ich liczby spełniają postawione przez nią kryteria.

Kiedy program został ukończony, Wiktoria przekazała go mieszkańcom wioski, a ci entuzjastycznie zaczęli go używać. Na przykład, gdy ktoś wprowadził liczbę 145, program błyskawicznie odpowiedział, że 145 można przedstawić jako sumę różnych silni: 1! + 4! + 5! = 1 + 24 + 120 = 145. Wioska Fraktalocja stała się jeszcze bardziej zafascynowana liczbami i matematyką, a Wiktora zyskała sławę jako twórczyni niezwykłych programów. Jej dzieło pomogło ludziom odkryć fascynujące zależności między liczbami i cieszyć się magią matematyki.

Wejście

W pierwszym wierszu jedna liczba naturalna q określająca liczbę zapytań (nie większa niż 10⁵).

W kolejnych wierszach q liczb naturalnych z przedziału [1..10¹⁸].

Wyjście

Dla każdego zapytania napis TAK, jeśli liczba jest sumą różnych silni lub napis NIE w przeciwnym razie.

Przykład

5
1
485838
376697439861264
6267345849
7

TAK
NIE
TAK
TAK
TAK