SOLVE
LATER
Rjit being fond of traveling, needs some leaves from his office for the same. Once in his office, the Monk claimed that no one can split the given array of N elements into less than or equal to K \(Special \; Subsequences\). Being greedy for leaves, Rjit accepted his challenge.
In case Rjit succeeds in the challenge, and let's say he found X \(Sepecial \; Subsequences\) in the array, then he will get \(K-X\) number of leaves.
\(Special \; Subsequences\) should follow the conditions mentioned below:
Help Rjit to maximize the number of leaves. In case Rjit fails in Monk's challenge, print 1.
Note: We consider a splitting of the array to be valid, if each element of the array occurs in exactly one \(Special \;Subsequence\) present in the split.
Input format:
The first line contains T, the number of test cases. For each test case, two integers N and K will be given. Following that line, the next line contains N space separated integers denoting array elements \(A_i\) of array A.
Output format:
You've to print 1, if Rjit fails in Monk's challenge, else print the maximum leaves he can get.
Constraints:
1 ≤ T ≤ \(10\)
1 ≤ N ≤ \(10^5\)
1 ≤ K ≤ \(10^5\)
1 ≤ A_{i} ≤ \(10^9\)
Sample Input-0:
1
4 1
4 3 2 1
Sample output-0:
0
Sample explanation-0:
Here Rjit will find 1 \(Special \; Subsequence\) that is \(4,3,2,1\). So number of leaves he will get is \(K-1 = 1-1 = 0\).
Here Rjit fails in Monk's challenge, and not able to find number of Special Subsequences less than or equal to K. So answer is 1.