小w 很喜欢 gcd\gcdgcd 和集合，于是他想出了这道题。但是 小w 还很喜欢看书，出完这道题他就跑去图书馆了。你能帮他解决这个问题吗？
称一个集合的 gcd\gcdgcd 为集合内所有数的最大公因数。
形式化地，若集合 A={a1,a2,...,an}A=\left \{ a_1,a_2,...,a_n \right \}A={a1,a2,...,an} ，则 gcd(A)=gcd(a1,a2,...,an)\gcd(A)=\gcd(a_1,a_2,...,a_n)gcd(A)=gcd(a1,a2,...,an)。
特别地，如果集合只有一个数，则它的 gcd\gcdgcd 是就是这个数，即 gcd({a})=a\gcd(\left \{ a \right \})={a}gcd({a})=a。
给定一个大小为 nnn 的不可重数集 UUU，你需要将其划分为 kkk 个非空子集，使得每个子集的 gcd\gcdgcd 的和最大。
第一行，一个整数 t(1≤t≤104)t(1 \le t \le 10^4)t(1≤t≤104)，代表数据组数。
对于每组数据:
第一行，输入 222 个整数 n,kn,kn,k (1≤k≤n≤106)(1 \le k \le n \le 10^6)(1≤k≤n≤106)，分别表示集合 UUU 的大小和划分的子集数。
第二行，输入 nnn 个整数 a1,...,ana_1,...,a_na1,...,an (1≤ai≤106)(1 \le a_i \le 10^6)(1≤ai≤106)，aia_iai 互不相同，表示给定的集合 UUU。
保证同一测试点内的 aia_iai 的最大值之和不超过 10610^6106 。
输出一个整数，代表每个子集的 gcd\gcdgcd 的和的最大值。
输入样例
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
输出样例
8 38 6 10
