Problems
Sum of GCD
Sum of GCD
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.
\sum_{\mathclap{1 \le i < j\le n}} GCD(a_i,a_j)
Input data
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 10^6.
Output data
For each test, print the sum of the GCDs of all possible pairs on a separate line.
Examples
Input example #1
3 4 10 20 30 40 3 7 5 12 3 125 15 25
Output example #1
70 3 35
Note
The answer for the third example is
GCD(125,15) + GCD(125,25) + GCD(15,25) = 5 + 25 + 5 = 35