seuOJ532 - GCD of Set

小w 很喜欢 $\gcd$ 和集合，于是他想出了这道题。但是小w 还很喜欢看书，出完这道题他就跑去图书馆了。你能帮他解决这个问题吗？

称一个集合的 $\gcd$ 为集合内所有数的最大公因数。

形式化地，若集合 $A=\left \{ a_1,a_2,...,a_n \right \}$ ，则 $\gcd(A)=\gcd(a_1,a_2,...,a_n)$ 。

特别地，如果集合只有一个数，则它的 $\gcd$ 是就是这个数，即 $\gcd(\left \{ a \right \})={a}$ 。

给定一个大小为 $n$ 的不可重数集 $U$ ，你需要将其划分为 $k$ 个非空子集，使得每个子集的 $\gcd$ 的和最大。

第一行，一个整数 $t(1 \le t \le 10^4)$ ，代表数据组数。

对于每组数据:

第一行，输入 $2$ 个整数 $n,k$ $(1 \le k \le n \le 10^6)$ ，分别表示集合 $U$ 的大小和划分的子集数。

第二行，输入 $n$ 个整数 $a_1,...,a_n$ $(1 \le a_i \le 10^6)$ ， $a_i$ 互不相同，表示给定的集合 $U$ 。

保证同一测试点内的 $a_i$ 的最大值之和不超过 $10^6$ 。

输出一个整数，代表每个子集的 $\gcd$ 的和的最大值。

输入样例

4
3 2
3 6 5
5 4
13 11 10 9 5
4 2
4 2 5 3
4 3
4 2 5 3

输出样例