human
A median of an array of integers of length n is the number standing on the ⌈ {n/2} ⌉ (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting with 1. For example, a median of the array [2, 6, 4, 1, 3, 5] is equal to 3. There exist some other definitions of the median, but in this problem, we will use the described one.

Given two integers n and k and non-decreasing array of nk integers. Divide all numbers into k arrays of size n, such that each number belongs to exactly one array.

You want the sum of medians of all k arrays to be the maximum possible. Find this maximum possible sum.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. The next 2t lines contain descriptions of test cases.

The first line of the description of each test case contains two integers n, k (1 ≤ n, k ≤ 1000).

The second line of the description of each test case contains nk integers a_1, a_2, …, a_{nk} (0 ≤ a_i ≤ 10^9) — given array. It is guaranteed that the array is non-decreasing: a_1 ≤ a_2 ≤ … ≤ a_{nk}.

It is guaranteed that the sum of nk for all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case print a single integer — the maximum possible sum of medians of all k arrays.

Example

Input

6
2 4
0 24 34 58 62 64 69 78
2 2
27 61 81 91
4 3
2 4 16 18 21 27 36 53 82 91 92 95
3 4
3 11 12 22 33 35 38 67 69 71 94 99
2 1
11 41
3 3
1 1 1 1 1 1 1 1 1

Output

165
108
145
234
11
3

Note

The examples of possible divisions into arrays for all test cases of the first test:

Test case 1: [0, 24], [34, 58], [62, 64], [69, 78]. The medians are 0, 34, 62, 69. Their sum is 165.

Test case 2: [27, 61], [81, 91]. The medians are 27, 81. Their sum is 108.

Test case 3: [2, 91, 92, 95], [4, 36, 53, 82], [16, 18, 21, 27]. The medians are 91, 36, 18. Their sum is 145.

Test case 4: [3, 33, 35], [11, 94, 99], [12, 38, 67], [22, 69, 71]. The medians are 33, 94, 38, 69. Their sum is 234.

Test case 5: [11, 41]. The median is 11. The sum of the only...
Solve the task in PYTHON3.
 ... What is a Python program to find this maximum possible sum?
assistant
#Here is Python program to find this maximum possible sum.

#------------------------template--------------------------#
import os
import sys
from math import *
from collections import *
# from fractions import *
# from heapq import*
from bisect import *
from io import BytesIO, IOBase
def vsInput():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
ALPHA='abcdefghijklmnopqrstuvwxyz/'
M=1000000007
EPS=1e-6
def Ceil(a,b): return...