\(M\) people are working in a call center. Each minute, exactly one customer will call for assistance, this is denoted by an array \(A\) of \(N\) elements : customer \(x\) will need assistance each minute \(i\) such as \(A_i = x\).
An employee can give assistance to one customer at a time. Assistance will last for an amount of time strictly less than one minute, after that he can either put the customer on hold and give assistance to another one or keep the line open waiting for another request from the same customer, even if no other calls from that customer are expected.
What is the minimum number of times customers must be put on hold so that employees can give assistance to everybody.
The first line of the input file contains one integer \(T \leq 30\) the number of test cases.
Each test case starts with a line with two integers \(N\) the number of calls and \(M\) the number of employees (\(1 \leq M, N \leq 10^5\)).
Then follows a line with \(N\) space separated integers \(A_i\) (\(1 \leq A_i \leq 10^5\)).
For each test case output in a new line one integer : the number of times you will need to put customers on hold.
- (\(30\) points) \(N, M \leq 100\).
- (\(30\) points) \(N,M \leq 1000\).
- (\(40\) points) No additional constraint.
1 5 2 1 2 3 1 2
One possible solution to the example is not putting on hold customer 1 : one employee will keep the line open with customer number \(1\), this employee cannot answer any call from customers different than \(1\). The other one will answer the call from \(2\), then put them on hold and answer \(3\), then put them on hold and answer \(2\).