You are given an array $a$ of $n$ positive integers.

Rearrange its elements in any order. If the resulting array is $b_1, b_2, \ldots, b_n$, its value is

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

the sum of the least common multiples of all pairs of adjacent elements.

Find the maximum value over all rearrangements of $a$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10$): the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100\,000$): the number of elements in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 7$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $100\,000$.

Output

For each test case, print a single integer: the maximum possible value.

Examples

Input 1

1
2
5 2

Output 1

10

Input 2

1
6
2 2 2 3 3 3

Output 2

30