说明

斐波那契数列，又称黄金分割数列。该数列具有神奇的特性：数列中每一数字都是其前面两个数字之和。前一数字与后一数字之比趋近于固定常数 0.618。

斐波那契数列的定义为： k=0 或 1 时， F[k]=k； k>1 时， F[k]=F[k-1]+F[k-2]。

数列的前几项为 0， 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89， 144…。

由此可以推算出：当 k=45 时， F(45)＞1e9

编程任务是， 判断给定的数字 $n_i (0≤n_i≤1e9)$ 能否表示成两个斐波那契数的乘积。

输入格式

第一行包含一个整数$t(1≤t≤10)$，表示询问数量

接下来 1行$i$个数$n_i(0≤n_i≤1e9)$，空格隔开

输出格式

共 t 行，第 i 行为 TAK（是）或 NIE（否），表示 $n_i$ 能否被表示成两个斐波那契数的乘积

样例

5
5 4 12 11 10

TAK
TAK
NIE
NIE
TAK

数据范围

• 对于 50% 的数据，$1 ≤ n ≤ 1e4$
• 对于 100% 的数据，$1 ≤ t ≤10， 1 ≤ n ≤ 1e9$