You are given an array $$$a$$$ of length $$$n$$$, and an integer $$$k$$$. Let $$$f(l,r)$$$ be the value of $$$\operatorname{mex}(a_l,a_{l+1},\ldots,a_r)$$$$$$^{\text{∗}}$$$. You want to perform the following operation $$$n-k+1$$$ times:

Let the current length of the sequence be $$$|a|$$$. You need to find an interval $$$[l, r]$$$ of length $$$k$$$ such that $$$\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r).$$$ In other words, you need to select a window of size $$$k$$$ such that among all windows of size $$$k$$$, the window you selected has the maximum $$$\operatorname{mex}$$$. If multiple $$$[l,r]$$$ exist, you may select any. Then, you must select any integer $$$i$$$ such that $$$l \leq i \leq r$$$, and delete $$$a_i$$$ from $$$a$$$. That is, your new sequence will be $$$[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$$$.

For example, in the array $$$[1,2,0,1,3,0]$$$ with $$$k=3$$$, the two possible $$$(l,r)$$$ pairs are $$$(1,3)$$$ and $$$(2,4)$$$ (since they each have $$$\operatorname{mex} 3$$$, which is the maximum among all windows of size $$$3$$$). Therefore, you can remove any one of the indices $$$1,2,3,4$$$ in your next move.

After $$$n - k + 1$$$ operations, you will have a sequence of length $$$k-1$$$. Your objective is to maximize the $$$\operatorname{mex}$$$ of the remaining elements. Please output the maximum $$$\operatorname{mex}$$$ possible.

$$$^{\text{∗}}$$$The minimum excluded (MEX) of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Input

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

The first line of each test case contains two positive integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$).

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

Output a single non-negative integer representing your answer.

Note

In the first test case, we can select the interval $$$[1,3]$$$. Then, delete $$$a_2$$$ to obtain $$$[0,0]$$$. The process terminates, and the $$$\operatorname{mex}$$$ of the remaining elements is $$$1$$$.

In the third test case, we can perform the following operations:

Select $$$i=1,j=3$$$. This is allowed because the $$$\operatorname{mex}$$$ of all windows of size $$$3$$$ is $$$3,0,3$$$, and the window $$$[1,3]$$$ has a $$$\operatorname{mex}$$$ of $$$3$$$, which is the largest. Then, remove $$$a_2$$$. The sequence is now $$$[0,2,1,0]$$$.
Select $$$i=2,j=4$$$. Then, remove $$$a_2$$$. The sequence is now $$$[0,1,0]$$$.
Select $$$i=1,j=3$$$. Then, remove $$$a_1$$$. The sequence is now $$$[1,0]$$$. The process terminates, and the final $$$\operatorname{mex}$$$ is $$$2$$$.

Yet Another MEX Problem

Examples