题目描述

题目译自 PA 2014 Runda próbna Iloczyn

斐波那契数列是一个著名的整数序列，递归定义如下：

$$F_{k}=\left\{\begin{array}{cl} k & \text{对于 } k \in\{0,1\} \\ F_{k-1}+F_{k-2} & \text{对于 } k>1 \end{array}\right. $$

以下是该序列的前几项：

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$$

在本题中，我们需要检查给定的整数是否可以表示为两个斐波那契数的乘积。

输入格式

输入数据的第一行包含一个整数 $t$ $(1 \leq t \leq 10)$，表示测试数据组数。

接下来有 $t$ 行，第 $i$ 行包含一个整数 $n_{i}$ $(0 \leq n_{i} \leq 10^{9})$。

输出格式

输出恰好 $t$ 行。第 $i$ 行应包含一个字符串 TAK 或 NIE，表示数字 $n_{i}$ 是否可以表示为两个斐波那契数的乘积。

5
5
4
12
11
10

TAK
TAK
NIE
NIE
TAK