Byteman Laugh 教授获得了一个难得的机会。他被告知，如果他的研究能得到“邪恶字节教授援助基金会”的认可，他就能获得一百万美元的资助。教授总是尽其所能让他的研究变得有趣。现在是社会对教授的工作进行评估的时候了。

然而，这并不容易。教授距离展示研究成果只剩下一周的时间了。像每一位科学家一样，Laugh 教授有点心不在焉。他把研究结果弄丢了，所以他请求你编写一个程序来重现它们。

Laugh 教授不喜欢让他的朋友和同事感到无聊。因此，他感兴趣的不是普通的积分，而是令人兴奋且震撼的素数。

对于一个大于 2 的素数 $p$，一个大于 1 的整数 $e$，以及一个小于 $p$ 的整数 $n$，教授称 $n$ 是 $(p, e)$-有趣的，如果存在一个自然数 $x$ 使得 $x^{e} \equiv n \pmod p$。换句话说，$x^{e}$ 和 $n$ 除以 $p$ 的余数相同。

编写一个程序，完成以下任务：

• 读取一个素数 $p$、一个指数 $e$ 以及一个数字序列；
• 测试该序列中的每个数字是否为 $(p, e)$-有趣的；
• 输出结果。

我们称一个大于 1 且除了 1 和它本身外没有其他正整数约数的整数为素数。

输入格式

第一行包含两个由空格分隔的整数：一个素数 $p$ 和一个数字 $e$ ($3 \le p \le 2^{32}$, $2 \le e < 2^{32}$)。第二行包含一个整数 $k$，即测试用例的数量 ($1 \le k \le 15$)。接下来的 $k$ 行，每行包含一个整数。其中第 $i$ 行包含一个数字 $n_{i}$，$1 \le n_{i} \le p - 1$。

输出格式

你的程序应输出恰好 $k$ 行。第 $i$ 行 ($1 \le i \le k$) 应包含一个单词：如果 $n_{i}$ 是 $(p, e)$-有趣的，则输出 TAK（波兰语中的“是”）；如果不是，则输出 NIE（波兰语中的“否”）。

样例

输入格式 1

17 2
5
1
9
3
7
6

输出格式 1

TAK
TAK
NIE
NIE
NIE