Sum of GCD

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

For the given $n$ positive integers $a_{1}, a_{2}, ..., a_{n}$ , find the sum of the GCD (greatest common divisor) of all possible pairs of these numbers.

1 \leq i < j \leq n \sum GC D (a_{i}, a_{j})

Input

The first line contains the number of test cases $t (1 < t < 100)$ . Each test consists of one line containing the number $n (1 < n < 100)$ , followed by $n$ positive integers. All input integers do not exceed $1 0^{6}$ .

Output

For each test, print the sum of the GCDs of all possible pairs on a separate line.

Examples

Input #1

Answer #1

Note

The answer for the third example is

GC D (125, 15) + GC D (125, 25) + GC D (15, 25) = 5 + 25 + 5 = 35

Submissions 2K

Acceptance rate 62%