P5993 [PA 2014] Iloczyn

Translated from PA 2014 Trial Round.

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.

The first line contains an integer $T$, representing the number of queries. The next $T$ lines each contain an integer $n_i$.

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.

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