You are given an array $a$ with $n$ integers. You can perform the following operation at most $k$ times:

• Choose two indices $i$ and $j$, in which $i \,\bmod\, k = j \,\bmod\, k$ ($1 \le i \lt j \le n$).
• Swap $a_i$ and $a_j$.

After performing all operations, you have to select $k$ consecutive elements, and the sum of the $k$ elements becomes your score. Find the maximum score you can get.

Here $x \bmod y$ denotes the remainder from dividing $x$ by $y$.

Input

The first line contains one integer $t$ ($1 \le t \le 600$) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the length of the array and the number in the statement above.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)  — the array itself.

Output

For each test case, print the maximum score you can get, one per line.

Note

In the first test case, we can get a score of $11$ if we select $a_1, a_2$ without performing any operations.

In the third test case, we can get a score of $15$ if we first swap $a_1$ with $a_4$ and then select $a_3, a_4, a_5$.

Samples

5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997

11
7
15
10
2999999997