Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given an Array \(A[]\), length of the array is N. You need to find out largest subarray with length exactly K and sum is maximum.
For example, \(A[]\)= {3,5,6,2,4} and K=3,
all possible subarray from A[] with length K are,
{3,5,6},{5,6,2},{6,2,4}.
Before you find maximum subarray sum, you can do following operation as many times as you wish,

• Choose two indices i and j, if gcd of their value is greater than 1, gcd\((A[i],A[j]) > 1\) ,you can swap their elements. (ex. swap\((A[i],A[j])\))

gcd means greatest common divisor.
Example : gcd(4,6)=2, gcd(3,9)=3 ect.

Input

First Line, T number of test case.
In each test case,
First Line N and K.
Second Line an Array A[].

\(1<=T<=10^3\)
\(1<=N<=6 * 10^3\)
\(1<=K<=N\)
\(1<=A[]<=10^9\)

It is gurantee that sum of N overall test case does not exceed \(6 * 10^3\).

Output

In each test case, Print the maximum sum.

Sample

2
6 3
1 6 3 6 2 7
3 1
1 2 3

19
3

First test case,
Intially Array \(A []\) = {1,6,3,6,2,7}; and K = 3.
If we choose indices 2 & 5, gcd(A[2],A[5])= gcd(6,2) = 2, which is greater than 1.
We can swap their value. After swap array look like,
\(A[]\) = {1,2,3,6,6,7}.
Now we can select subarray, 4 to 6, {6,6,7} and their sum is 19 which is maximum.