eolymp
bolt
Try our new interface for solving problems
Problems

Sum of GCD

Sum of GCD

Time limit 1 second
Memory limit 128 MiB

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
Source 2013 ACM-ICPC Asia Phuket Regional Programming Contest, Practice Session, November 21