E. Max Mex Bamboza
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

After the debate with Ahmad, Ammar went to B.Laban to eat his favorite Mango Bamboza. But when he went there, he found out that B.Laban has nothing other than "Matrix Bel Lotus". Very angry, he went home to play with his array $$$a$$$ of $$$n$$$ integers and his empty array $$$b$$$.

Ammar decided to do the following:

  • He will choose exactly $$$k$$$ non-empty subsequences from $$$a$$$(they could intersect), calculate the mex of each subsequence, and add it to array $$$b$$$.
  • He will calculate $$$X$$$, the mex of array $$$b$$$.
  • He will eat $$$X$$$ Mango Bambozas from his fridge(yes, Ammar has infinite Bambozas in his fridge, but he went to B.Laban to eat fresh ones).

Now Ammar wonders what is the maximum number of Bambozas he could eat if he chooses the subsequences optimally?

The MEX(minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The MEX of $$$[2,2,1]$$$ is $$$0$$$ because it is not in the array.
  • The MEX of $$$[2,2,0]$$$ is $$$1$$$ because $$$0$$$ is in the array but $$$1$$$ is not.

A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array $$$[5,3,1,2,4]$$$ the following arrays are subsequences: $$$[3]$$$ , $$$[5,3,1,2,4]$$$ , $$$[5,1,4]$$$ , but the array $$$[1,3]$$$ is not.

Input

The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases.

The first line of each testcase consists of two integers $$$n , k \: (1 \leq n \leq 3 \cdot 10^5) (1 \leq k \leq min(10^{16} , 2^n -1) )$$$ .

The second line of each testcase consists of $$$n$$$ integers $$$a_i (0 \leq a_i \leq 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each testcase, print a single integer, the maximum number of Bambozas Ammar could eat.

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