For the given n positive integers a1,a2,...,an, find the sum of the GCD (greatest common divisor) of all possible pairs of these numbers.
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 106.
For each test, print the sum of the GCDs of all possible pairs on a separate line.
The answer for the third example is