Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

SUMGCD - Sum of GCD


Given “n” positive integers, you have to find the summation of GCD (greatest common divisor) of every possible pair of these integers.

Input

The first line of the input contains an integer denoting the number of test cases. The description of Ttest cases follows. Each test case, described in a single line, contains “n+1” space-separated integers: The first one is the number “n” (1 < n < 100) indicating the number of input integers, the remaining ones includes “n” positive integers. Note that each input integer do not exceed 106.

Output

For each test case, output the sum of the GCDs of every possible pair.

Example

Input:
3
4 10 20 30 40
3 7 5 12
3 125 15 25
Output: 70
3
35

Added by:mbk_live
Date:2019-01-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PYTHON PYTHON3 SWIFT