[PA2014] Iloczyn

题目描述

斐波那契数列的定义为：

• $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,…$。

你的任务是判断给定的数字能否被表示成两个斐波那契数的乘积。

输入格式

第一行包含一个整数 $T$，表示询问数量。

接下来的 $T$ 行，每行一个整数 $n_i$。

输出格式

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

样例 #1

样例输入 #1

5
5
4
12
11
10

样例输出 #1

TAK
TAK
NIE
NIE
TAK

提示

对于 $100\%$ 的数据，$1\le T\le 10$，$0\le n_i\le 10^9$。