Description

对于一个序列 $a_1,a_2,\cdots , a_n$ ，定义 $f(i)$ 表示序列前 $i$ 项的最大公约数。我们认为一个序列的价值为 $\sum_{i=1}^n{f(i)}$。

现在给你一个序列 $a_1,a_2,\cdots , a_n$，你需要把它重新排列，使得序列的价值尽量大。

Input Format

输入包含多组数据。

第一行为一个整数 $T$ 表示数据的组数。

每组数据包括两行。

第一行一个正整数 $n$，表示序列的长度。

第二行 $n$ 个正整数 $a_1,a_2,\cdots , a_n$，表示序列的第 $i$ 项。

Output Format

输出文件包含 $T$ 行，每行一个整数，第 $i$ 行表示第 $i$ 组数据的答案（即序列最大价值）。

Sample

输入样例：

2
4
1 2 3 4
3
5 10 15

输出样例：

8
25

Hint

对于 $10\%$ 的数据，$1\le n\le 9$；

对于 $30\%$ 的数据，$1\le n\le 16$；

对于 $100\%$ 的数据，$1\le n\le 100000，1\le a_i\le 100000，1\le T\le 20$。