#P18115. Hamiltonian LCM

Hamiltonian LCM

Hamiltonian LCM

时间限制:7秒。空间限制:1024MiB。标准输入输出。

给定一个长度为 nn 的正整数数组 aa。你可以任意重排它,得到 b1,…,bnb_1,\ldots,b_n。重排的价值为

∑i=1n−1lcm⁡(bi,bi+1),\sum_{i=1}^{n-1}\operatorname{lcm}(b_i,b_{i+1}),

其中 lcm⁡\operatorname{lcm} 表示最小公倍数。求最大可能价值;只输出最优值,不需要输出排列。

输入格式

第一行整数 TT,1≤T≤101\le T\le10。

每组数据第一行整数 nn,1≤n≤1000001\le n\le100000;第二行 nn 个整数 aia_i,1≤ai≤71\le a_i\le7。

所有数据的 nn 之和不超过100000。

输出格式

每组输出一行最大价值。n=1n=1 时空和为0。

样例1

1
2
5 2
10

样例2

1
6
2 2 2 3 3 3
30