Doge and Cate can no longer coexist in the same planet. Time has finally come to decide once and for all, who will reign over this planet.
They agreed on a non violent way to settle this. Both are given an array of N integers and a positive integer K. In a single operation, one can change an element of the array to any value. The task is to transform the array such that there exists an integer X, for which there are exactly K elements in the array having their value as X.

Cate being a stupid creature can never solve this. Doge being an elite creature, takes it to another level by achieving the task using minimum number of operations. Given the array and K, find the minimum number of operations required.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains integers N and K. The second line contains N space-separated integers denoting the array A.

Output
For each test case, output a single line containing the minimum number of operations required.

Constraints

1 ≤ T ≤ 100
1 ≤ N ≤ 1000
1 ≤ K ≤ N
1 ≤ Ai ≤ 10^9

Example
Input:
2
5 1
1 2 3 4 5
4 3
1 2 2 1
Output:
0
1

见题面

见题面