You are given \(N\) types of blocks.

There are \(A[i]\) blocks of the type \(i\) \((0 \leq i \leq N-1)\) .

You have to make groups of size \(K\), such that no group has more than \(floor(K/2)\) blocks of the same type.

Find the maximum number of groups that you can make.

Input Format:

The first line contains an integer \(T\), denoting the number of test cases.
The first line of each test case contains two space separated integers \(N\) and \(K\) which denotes the length of the array \(A\) and the size of the group.
The second line of each test case contains \(N\) space separated positive integers, denoting elements of array \(A\)

Output Format:

An integer denoting the maximum number of groups that you can make satisfying the given condition.

Constraints:

\(1 \leq T \leq10\)
\(1 \leq N \leq 10^5 \)
\(2 \leq K \leq N\)
\(1 \leq A[i] \leq 10^6 \)
The sum of \(N\) over all test cases does not exceed \(3*10^5\)