eolymp
Competitions

DSA Week 2

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 determines the number of test cases n (1 < n < 100). The following n lines are the n test cases. Each test case contains 2 parts: first part is the number m (1 < m < 100) indicating the number of input integers, second part includes m positive integers. The input integers do not exceed 1000000.

Output

For each test case, show the summation of GCDs of every possible pair.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
4 10 20 30 40
3 7 5 12
3 125 15 25
Output example #1
70
3
35
Source 2013 ACM-ICPC Asia Phuket Regional Programming Contest, Practice Session, November 21