405178: GYM101810 F Minimum Sum of Array

You are given an array a consisting of n integers a₁, ..., a_n. In one operation, you can choose 2 elements a_i and a_j in which a_i is divisible by a_j and transform a_i to a_j.

A number x is said to be divisible by a number y if x can be divided by y and the result is an exact whole number. For example, 15 is divisible by 3, because 15÷ 3 = 5 exactly, but 9 is not divisible by 2 because 9÷ 2 is 4 with 1 left over.

Your task is to find the minimum sum of the array a that can be obtained by making as many transform operations as you want. Can you?

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 10⁵), in which n is the size of array a. Then a line follows containing n integers a₁, ..., a_n (1 ≤ a_i ≤ 10⁶), giving array a.

The sum of n overall test cases does not exceed 3 × 10⁶.

For each test case, print a single line containing the minimum sum of the array a that can be obtained after making as many transform operations as you want.

1
5
2 2 3 6 6

11