# [Solution] Minimum Sum solution codechef

## Minimum Sum solution codechef

Minimum Sum solution codechef – You are given an array A_1, A_2, \dots, A_N of length N. You can perform the following operation any number of times (possibly 0 times) :

• Choose two distinct indices i and j and replace either A_i or A_j with \gcd(A_i,A_j).

Find the minimum possible sum (ie. A_1 + A_2 + \dots + A_N) that you can achieve, and output that.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first line of each test case contains an integer N – the length of the array A.
• The second line of each test case contains N space-separated integers A_1,A_2,\ldots,A_N.​

### Output Format

For each test case, output on a new line the minimum sum of the array that can be achieved.

## [Solution] Minimum Sum solution codechef

• 1 \leq T \leq 100
• 2 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• The sum of N over all test cases won’t exceed 3 * 10^5.

### Sample 1:

Input

Output

2
2
5 10
3
2 2 6

10
6


## [Solution] Minimum Sum solution codechef Explanation

Test case 1: Choose i=1,j=2 and replace A_2 with \gcd(5,10)=5.

Test case 2: Choose i=1,j=3 and replace A_3 with \gcd(2,6)=2.