Given N types of flowers, each type i, there are F[i] number of the flowers.
Given integer K, you need to make up groups of flowers with K flowers for each group; no group should have 
more than floor(K/2) flowers of each type. Please find the maximum number of groups of flowers you can make.

Input:
The first line contains an integer T which is the test cases.
The first line of each test case is integer N and K for each case.
The second line of each test case contains N integers which are list of F.


1 <= T <= 10
1 <= N <= 100,000
2 <= K <= N
1 <= F[i] <= 1,000,000
The sum of N over all the test cases <= 300,000

Output:
For each test case, 
One integer which is the maximum number of group you can make