F. 数组值

• 时间限制：每个测试点 $4$ 秒
• 内存限制：每个测试点 $256$ 兆字节

你有一个由非负整数组成的数组 $a_1, a_2, \dots, a_n$。

一个长度至少为 $2$ 的子数组 $a[l, r] = [a_l, a_{l+1}, \dots, a_r]$ 的值定义为满足 $l \le i < j \le r$ 的所有 $a_i \oplus a_j$ 的最小值，其中 $\oplus$ 表示异或（exclusive-or）运算。

你需要求出所有长度至少为 $2$ 的子数组的值中第 $k$ 小的那个值。

输入

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le \frac{n \cdot (n-1)}{2}$）。

每个测试用例的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$），即数组本身。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出

对于每个测试用例，输出一个整数，表示所有长度至少为 $2$ 的子数组的值中第 $k$ 小的值。

示例

输入

4
5 2
1 2 3 4 5
2 1
4 3
4 6
1 2 4 8
5 9
1 2 3 4 5

输出

1
7
12
3

注

在第一个测试用例中，所有子数组及其最小异或对的值如下：

• $[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$

排序后为：$1,1,1,1,1,1,1,1,3,7$。因此第 $2$ 小的值为 $1$。