For the given positive integers , 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 . Each test consists of one line containing the number , followed by positive integers. All input integers do not exceed .
For each test, print the sum of the GCDs of all possible pairs on a separate line.
The answer for the third example is