Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given an array \(A[]\) and the length of the array is N. You need to rearrange array \(A[]\) such way that sum of GCD odd index and even index is as maximum as possible.

Let's see,

• Odd index GCD of array \(A[]\), X = GCD \((A_1, A_3, A_5,...A_N)\). (all odd index 1 to N)

• Even index GCD of array \(A[]\), Y = GCD \((A_2, A_4, A_6,...A_N)\). (all even index 1 to N)

After rearrange of array \(A[]\), Find Maximum possible sum of X+Y.

GCD means Greatest Common Divisor. For example,

GCD(2,4,6) = 2, that means 2 is the largest possible number which divide all number appear in the set.

Note : The only difference between Easy version and Hard version limit of N and array A[].

Input

T : Number of Test case.
N : Length of the array A[].
A[] : Number of element exactly N.

\(1 <= T <= 5\)
\(2 <= N <= 10^5\)
\(1 <= A[] <= 10^5\)

Output

In each test case, print the maximum sum.

Sample

2
5
12 27 21 14 15
2
2 5

10
7

First test case: