给定一个正整数 $n$，判断其是否可以将其表示为 $k$ 个不同的正整数的乘积。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 4\,000$)，表示要考虑的测试用例的数量。接下来的 $t$ 行中的每一行包含两个整数 $n_{i}$ 和 $k_{i}$ ($1 \le n_{i} \le 10^{9}$，$1 \le k_{i} \le 20$)。

输出格式

你的程序应该输出恰好 $t$ 行。这些行中的第 $i$ 行应该包含一个单词 TAK 或 NIE，取决于数字 $n_{i}$ 是否可以表示为 $k_{i}$ 个不同因子的乘积。

示例

输入

3
15 2
24 4
24 5

输出

TAK
TAK
NIE