Even Odd GCD (Easy Version)
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
Input  Output 



First test case:
Information
 ID
 1076
 Difficulty
 8
 Category
 Number_Theory Click to Show
 Tags
 # Submissions
 76
 Accepted
 7
 Accepted Ratio
 9%
 Uploaded By
Related
In following contests: