第 2 题 数字过程 (numberprocess)

时间限制 30 s · 空间限制 64 MB · 24 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 numberprocess.in，输出文件 numberprocess.out。

• 题目代号：1ic
• 时间限制：30 s，内存限制：64 MB

题目描述

考虑函数 $f(n)$，它返回 $n$ 的各位数字之和。例如：$f(2019) = 2 + 0 + 1 + 9 = 12$。再考虑函数

例如：$g(2019) = 2019 + f(2019)^2 = 2019 + 12^2 = 2019 + 144 = 2163$。

Bajtazar 非常喜欢函数 $g$。他开始进行如下过程：从 $n = 1$ 开始，计算 $g(n)$ 并把结果作为新的 $n$；然后再计算 $g(n)$ 并再次更新 $n$，如此反复。这个过程得到的前四个数是 $1, 2, 6, 42$。

Bajtazar 有许多喜欢的数，对每一个他都想知道：这个数是否可能由他的过程得到？请你帮帮他！

对每个给出的数，判断它是否能由该过程得到并输出结果。

输入格式

第一行一个自然数 $Q$（$1 \le Q \le 100\,000$），表示询问数量。

接下来 $Q$ 行，每行一个自然数 $M_i$（$1 \le M_i \le 5 \cdot 10^9$），表示一个询问。

输出格式

输出恰好 $Q$ 行。第 $i$ 行对应第 $i$ 个询问的答案：若 $M_i$ 能由 Bajtazar 的过程得到，输出 TAK，否则输出 NIE。

样例

样例 1

输入：

6
2
1
30
42
2
731

输出：

TAK
TAK
NIE
TAK
TAK
NIE

样例 2

输入：

3
78
1806
4997888322

输出：

TAK
NIE
TAK

数据范围与子任务

完整数据满足 $1 \le Q \le 100\,000$，$1 \le M_i \le 5 \cdot 10^9$。

说明

过程产生的数称为「特殊数」。由于 $g(n) > n$，该序列严格递增。可以证明，不超过 $5 \cdot 10^9$ 的特殊数只有约 $2\,962\,717$ 个，数量足够少，使得预生成与排序后双指针问答查询成为可能。