提交时请开启 O2 优化，并使用较快的输入输出方式。

题目描述

定义集合 $S(t)=\{n^t\mid n\in\mathbb N_+\}=\{1^t,2^t,3^t,\cdots\}$。

现在给定 $k$ 个数 $a_1,a_2,\cdots,a_k$，炽火淀想知道 $\bigcup\limits_{i=1}^kS(a_i)$ 中第 $m$ 小的数字，其中 $\bigcup\limits_{i=1}^kS(a_i)=S(a_1)\cup S(a_2)\cup\cdots\cup S(a_k)$。请你帮帮她！

输入格式

本题有多组测试数据。

第一行一个正整数 $q$，表示测试数据个数。

对于每组数据，第一行为两个正整数 $m,k$，第二行为 $k$ 个用空格隔开的整数 $a_1,a_2,\cdots,a_k$。

输出格式

对于每组数据，输出一个整数，表示 $\bigcup\limits_{i=1}^kS(a_i)$ 中第 $m$ 小的数字。

样例

5
12 3
2 3 5
9 6
19 49 6 5 2 45
8 7
32 39 24 50 47 9 21
1 7
34 30 27 39 4 48 35
3 8
45 30 28 17 46 2 4 42

81
64
16777216
1
9

样例解释

对于第一组数据，$S(2)=\{1,4,9,16,25,36,49,64,81,\cdots\}$，$S(3)=\{1,8,27,64,125,\cdots\}$，$S(5)=\{1,32,243,\cdots\}$，$S(2)\cup S(3)\cup S(5)=\{1,4,8,9,16,25,27,32,36,49,64,\textcolor{red}{81},\cdots\}$。

数据范围

对于所有测试数据，$1 ≤ q ≤ 1000，1 ≤ m ≤ 10^9，1 ≤ k ≤ 50，1 ≤ a_i ≤ 50$，所 有 $a_i$ 互不相同，保证答案不超过 $10^{17}$。

• 子任务 1（15 分）：$m ≤ 200$；
• 子任务 2（20 分）：$m ≤ 5000$；
• 子任务 3（30 分）：$k ≤10$；
• 子任务 4（20 分）：$q ≤ 10$；
• 子任务 5（15 分）：无特殊限制。