Visitar URL original
Problem - 2277A - Codeforces


A. Subset Selecting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Olivia Rodrigo - the cure

You are given an array $$$a$$$ of $$$n$$$ integers and a positive integer $$$k$$$.

You want to split some of the elements of $$$a$$$ into groups $$$S_1, S_2, \ldots, S_m$$$ ($$$m \ge 0$$$) such that:

  • each group contains at least $$$k$$$ elements;
  • each element of $$$a$$$ belongs to at most one group (an element may also belong to no group at all).

Find the maximum possible value of $$$\operatorname{mex}(\{\max(S_1), \max(S_2), \ldots, \max(S_m)\})$$$ over all valid ways to form the groups, where $$$\operatorname{mex}(c)$$$ denotes the smallest non-negative integer that does not appear in the collection $$$c$$$. If $$$m = 0$$$, the collection is empty and $$$\operatorname{mex}(\{\}) = 0$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 100$$$) — the length of the array $$$a$$$ and the minimum allowed size of each group.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — the elements of the array $$$a$$$.

Output

For each test case, output a single integer — the maximum possible value of $$$\operatorname{mex}(\{\max(S_1), \max(S_2), \ldots, \max(S_m)\})$$$ over all valid ways to form the groups.

Example
Input
6
3 1
0 2 1
4 2
1 2 3 4
5 2
0 1 0 1 0
5 4
0 0 1 0 0
5 1
4 0 0 0 2
6 2
0 0 2 1 0 0
Output
3
0
2
1
1
3
Note

In the first test case, one optimal way is to form the groups $$$\{0\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, which gives $$$\operatorname{mex}(\{0, 1, 2\}) = 3$$$.

In the second test case, one optimal way is to form the single group $$$\{1, 2, 3, 4\}$$$, which gives $$$\operatorname{mex}(\{4\}) = 0$$$.

In the third test case, one optimal way is to form the groups $$$\{0, 0\}$$$ and $$$\{1, 1\}$$$, which gives $$$\operatorname{mex}(\{0, 1\}) = 2$$$.