G. Increasing Sequence
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a non-negative integer sequence $$$a$$$ of length $$$n$$$ and a constant value $$$k$$$.

Determine how many integers $$$x$$$ satisfy $$$x \in [0,k]$$$, such that $$$a_1 \oplus x, a_2 \oplus x, \ldots, a_n \oplus x$$$ forms a non-decreasing sequence.

Here, $$$\oplus$$$ denotes the XOR operation.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 2\cdot 10^5)$$$, indicating the number of test cases.

For each test case, the first line contains two integers $$$n,k$$$ $$$(1 \leq n \leq 2\cdot 10^5, 0 \leq k \leq 10^{18})$$$.

The second line contains $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \leq a_i \leq 10^{18})$$$.

The sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output a single line containing an integer representing the count of integers $$$x$$$ that satisfy the conditions.

Example
Input
1
4 17
3 2 5 16
Output
4