Minimum Array Sum After GCD Operations

You are given an array \(a_1, a_2, \dots, a_n\) of integers. You are allowed to perform the following operation any number of times (including zero): select any two distinct indices \(i\) and \(j\) (with \(i \neq j\)), and replace \(a_i\) with \(\gcd(a_i, a_j)\), where \(\gcd(x, y)\) denotes the greatest common divisor of \(x\) and \(y\).

Your task is to determine the minimum possible sum of the array after performing the operations optimally. It can be shown that the minimum sum is \(n \times G\), where \(G = \gcd(a_1, a_2, \dots, a_n)\) and \(n\) is the number of elements in the array.

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. Each test case consists of two lines. The first line contains an integer \(n\) — the number of elements in the array. The second line contains \(n\) space-separated integers representing the array \(a_1, a_2, \dots, a_n\).

outputFormat

For each test case, output a single line containing the minimum possible sum of the array after optimal operations.

1
3
12 15 18

9