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 **GCD**s of every possible pair.

Input example #1

3 4 10 20 30 40 3 7 5 12 3 125 15 25

Output example #1

70 3 35