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.
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$$.
You've to print $$-1$$, if Rjit fails in Monk's challenge, else print the maximum leaves he can get.
$$1$$ ≤ T ≤ $$10$$
$$1$$ ≤ N ≤ $$10^5$$
$$1$$ ≤ K ≤ $$10^5$$
$$1$$ ≤ Ai ≤ $$10^9$$
$$4$$ $$3$$ $$2$$ $$1$$
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$$.