Alice 和 Bob 是好朋友，尽管他们住在不同的国家，但他们彼此信任。有一天，Bob 有了一个将改变世界的创业想法。然而，他需要资金。Alice 同意给他所需的资金。由于 Bob 没有银行账户，Alice 告诉他，她会将钱转给住在 Bob 同一城市的共同好友 Eve，Bob 只需要告诉 Eve 秘密代码，她就会把钱交给他。

由于他们通过互联网进行交流，Alice 担心有人可能会窃听他们的谈话并听到秘密代码。Bob 是 Alice 见过的最聪明的人之一，所以她决定在通过某种函数进行哈希处理后将代码告诉 Bob，并且她知道，即使有人在窃听他们的谈话，Bob 仍然能够算出秘密代码。Bob 知道关于该代码的以下信息：

• 代码的长度为 $L$。
• 代码仅由字母 A-Z（仅大写）组成。
• 用于计算哈希值的公式为： $$((\sum_{i=1}^{L-1} n_i * M^{L-i}) + n_L) \% 10007$$
• $n_i$ 是表示索引为 $i$ 的字母的数值（$1 \le i \le L$），其中 A=0, B=1, C=2, ..., Z=25。
• 该代码是所有由字母 A-Z 组成且通过上述函数计算出的哈希值等于给定值 $H$ 的字符串中，字典序最小的一个。

你能帮 Bob 在别人算出代码之前快速找到它吗？

输入格式

输入包含一个或多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。

每个测试用例包含一行，由三个空格分隔的整数组成：

• $L$：秘密代码的长度（$1 \le L \le 100,000$）。
• $H$：代码的哈希值（$0 \le H < 10,007$）。
• $M$：哈希公式中使用的乘数（$0 \le M \le 20$）。

输出格式

对于每个测试用例，如果可以找到这样的字符串，则输出一行，包含该秘密代码；如果不存在这样的字符串，则输出 "None"（不含双引号）。

样例

输入格式 1

2
2 50 2
4 250 3

输出格式 1

NY
ARYZ