You have an array of non-negative integers $a_1, a_2, \ldots, a_n$.

The value of a sub-array of length $\ge 2$, $a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$ is the minimum value of $a_i \oplus a_j$ such that $l \le i < j \le r$, where $\oplus$ is the xor (exclusive-or) operator.

You have to find the $k$-th smallest value over all sub-arrays of length $\ge 2$.

Input

The first line of the input contains multiple test cases $t$ ($1 \le t \le 2 \cdot 10^4$).

The first line of each test case contains integer numbers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le \frac{n\cdot(n-1)}{2}$).

The second line of the input contains $n$ non-negative integer numbers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the array itself.

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

Output

Print the $k$-th smallest value obtained over all subarrays of length at least $2$.

见题面 Input 部分

见题面 Output 部分

In the first testcase, we have subarrays with their smallest exclusive-or pair as:

$[1,2]: 3$

$[2,3]: 1$

$[3,4]: 7$

$[4,5]: 1$

$[1,2,3]: 1$

$[2,3,4]: 1$

$[3,4,5]: 1$

$[1,2,3,4]: 1$

$[2,3,4,5]: 1$

$[1,2,3,4,5]: 1$

The sorted order would be: $1, 1, 1, 1, 1, 1, 1, 1, 3, 7$. Therefore, the second smallest element would be $1$.