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 **T **denoting the number of test cases. The description of **T**test 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 10^{6}.

### 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 25Output: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 |