Newton school

Hawkeye has been assigned to eliminate n monsters, the ith of which is of type ai. In one move, he can do either of the following:

i. Shoot down atmost any k monsters. In other words, he can shoot down any set of monsters such that the size of that set is smaller than or equal to k.
ii. Shoot down all monsters of any one type.

Find the minimum number of moves it will take him to shoot down all the monsters.

Input

The first line contains one integer t — the number of test cases. Each test case consists of two lines.
The first line contains two space-separated integers n and k.
The second line contains n space-separated integers a1, a2 . . . an.

Constraints:
1 ≤ t ≤ 105
1 ≤ k ≤ n ≤ 105
1 ≤ ai ≤ n
The sum of n over all test cases does not exceed 105.

Output

For each test case, print a single value - the minimum number of moves required

send the code please

Do not send the code. This question is from an ongoing contest.

3 Likes