随着年末临近，矮人法官决定将村庄的记数系统切换为基数为 $N$ 的进位制。对于大于 10 的基数，矮人们使用数字 0 到 9，随后是 A 到 Z 的大写英文字母。然而，所有问题的根源不在于法官，而在于矮人长老们。他们在查阅古籍后，决定禁用其中的某些数字。值得注意的是，数字 0 不在禁用列表中——毕竟，矮人们将其视为平衡的神圣象征。

编号系统是矮人有序社会的基石：每个村庄的房屋都使用最小的互不相同的正整数进行编号（使用正确的基数 $N$ 且不包含任何禁用数字）。法官想知道村庄中使用的最大房屋编号是多少。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量（即村庄的数量）。接下来的行包含各测试用例的描述。

每个测试用例的第一行包含三个整数 $N$、$K$ 和 $M$，以空格分隔，其中 $N$ 是进位制的基数，$K$ 是村庄中房屋的数量，$M$ 是禁用数字的数量。第二行包含 $M$ 个不同的禁用数字（以基数 $N$ 表示），以空格分隔。如果 $M = 0$，则第二行为空。

数据范围

$1 \le T \le 10\,000$ $2 \le N \le 36$ $0 \le M \le N - 2$ $1 \le K \le 10^{18}$

输出格式

对于每个测试用例，输出一行，包含村庄中最大的房屋编号（使用基数 $N$ 的进位制表示）。

样例

输入格式 1

6
3 5 1
1
9 7 1
7
2 100 0

7 123456789 3
3 6 1
16 123456789 3
1 A F
36 123456789 5
A X Z 2 4

输出格式 1

202
8
1100100
25224550520222
2E878582
6CO503