考虑以下无穷序列集合：

• 序列 #1，记作 $S(1)$，为 $1, 2, 3, \dots, n, \dots$；
• 序列 #2，记作 $S(2)$，为 $1, 4, 9, \dots, n^2, \dots$；
• 序列 #3，记作 $S(3)$，为 $1, 8, 27, \dots, n^3, \dots$；
• 以此类推；
• 序列 #$k$，记作 $S(k)$，为 $1, 2^k, 3^k, \dots, n^k, \dots$；
• 以此类推。

显然，这些序列中的每一个都是单调递增的。 我们称序列 $S(i_1, i_2, \dots, i_m)$ 为序列 $S(i_1), S(i_2), \dots, S(i_m)$ 的并集，如果：

• 序列 $S(i_1), S(i_2), \dots, S(i_m)$ 中的每个元素都属于 $S(i_1, i_2, \dots, i_m)$；
• 属于多个序列 $S(i_1), S(i_2), \dots, S(i_m)$ 的元素在 $S(i_1, i_2, \dots, i_m)$ 中仅出现一次；
• 序列 $S(i_1, i_2, \dots, i_m)$ 是单调递增的。

例如，$S(2, 3, 5)$ 为 $1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, \dots$ 你的任务是编写一个程序，处理一系列形式为“查找 $S(i_1, i_2, \dots, i_m)$ 的第 $N$ 个元素”的查询，其中 $N, m, i_1, i_2, \dots, i_m$ 为输入数据。

输入格式

输入的第一行包含一个整数，表示查询的数量 $q$ ($1 \le q \le 987$)。随后包含 $q$ 个查询。每个查询占用两行。每个查询的第一行包含 $N$ 和 $m$，其中 $N$ ($1 \le N \le 10^9$) 是要确定的元素的索引（从 1 开始），$m$ ($1 \le m \le 42$) 是要合并的序列数量。每个查询的第二行包含整数 $i_1, i_2, \dots, i_m$（所有整数均不相同，且都在 $1 \le i_k \le 50$ 范围内）。

输出格式

程序应为每个查询输出结果，每个结果占一行。保证答案不超过 $10^{17}$。

样例

输入 1

2
12 3
2 3 5
17 2
4 7

输出 1

81
38416