$n$ 個の正整数からなる配列 $a$ が与えられます。

その要素を任意の順序に並べ替えます。得られた配列が $b_1, b_2, \ldots, b_n$ であるとき、その値は

$$\operatorname{lcm}(b_1, b_2) + \operatorname{lcm}(b_2, b_3) + \ldots + \operatorname{lcm}(b_{n-1}, b_n),$$

すなわち、隣り合う要素のすべての組の最小公倍数の総和です。

$a$ のすべての並べ替えにわたる、この値の最大値を求めてください。

入力

最初の行には、テストケースの数を表す整数 $t$ ($1 \le t \le 10$) が1つ与えられます。

各テストケースの最初の行には、配列の要素数を表す整数 $n$ ($1 \le n \le 100\,000$) が1つ与えられます。

2行目には、$n$ 個の整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 7$) が与えられます。

すべてのテストケースにわたる $n$ の総和は $100\,000$ 以下であることが保証されます。

出力

各テストケースについて、可能な値の最大値を表す整数を1つ出力してください。

入出力例

入力 1

1
2
5 2

出力 1

10

入力 2

1
6
2 2 2 3 3 3

出力 2

30