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\)