Even Odd GCD (Hard Version)

Even Odd GCD (Hard Version)

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

Input Output
2
5
12 27 21 14 15
2
2 5
10
7

First test case:

Information

ID
1077
Difficulty
9
Category
Number_Theory Click to Show
Tags
# Submissions
106
Accepted
6
Accepted Ratio
6%
Uploaded By

Related

In following contests:

Bangladesh 2.0