Time Limit: 1.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 between 1 to N)

• Even index GCD of array \(A[]\), Y = GCD \((A_2, A_4, A_6,...A_N)\). ( all even index between 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 : Difference between easy and hard version is limit of N and array A[] elements.

Input

T : Number of test case.
N : Length of the array A[].
A[] : Exactly N elements.

\(1 <= T <= 100\)
\(2 <= N <= 100\)
\(1 <= A[] <= 100\)

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: