K. GCD of Set
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

小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$$$ 的和最大。

Input

第一行，一个整数 $$$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$$$ 。

Output

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

Example
Input
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
Output
8
38
6
10