Description

The Fibonacci sequence is defined as follows:

• When $k = 0$ or $1$, $F_k = k$.

• When $k > 1$, $F_k = F_{k - 1} + F_{k - 2}$.

The first few terms of the sequence are $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$.

Your task is to determine whether a given number can be represented as the product of two Fibonacci numbers.

Input Format

The first line contains an integer $T$, representing the number of queries.

The next $T$ lines each contain an integer $n_i$.

Output Format

Output a total of $T$ lines. The $i$-th line should be TAK (yes) or NIE (no), indicating whether $n_i$ can be represented as the product of two Fibonacci numbers.

5
5
4
12
11
10

TAK
TAK
NIE
NIE
TAK

Hint

For $100\%$ of the testdata, $1 \le T \le 10$, $0 \le n_i \le 10^9$.

Translated by ChatGPT 5