For non-negative integers $x, y$ and a positive integer $k$, let $S(x, y, k)$ be the set of values $(x + i) \oplus (y + j)$ for all $0 \le i, j \lt k$. Formally: $$ S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j \lt k \} $$ where $\oplus$ denotes the bitwise XOR operation.

Define $f(x, k)$ as the maximum size of $S(x, y, k)$ over all non-negative integers $y$ (that is, $y \ge 0$).

You are given integers $x$ and $k$. Compute $f(x, k)$.

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.

Each of the next $t$ lines contains two integers $x$ and $k$ ($1 \le x, k \le 10^{17}$).

Output

For each test case, output a single integer — the value of $f(x, k)$.

Note

In the first example, since $k=1$, the set $S$ will always contain exactly one element regardless of $y$. For instance, if we pick $y = 69$, we have $S(67, 69, 1) = \{67 \oplus 69\} = \{6\}$, so $|S(x, y, k)| = 1$.

In the second example, we have $x = 7$ and $k = 3$. The optimal choice is $y = 8$. The values of $(x + i) \oplus (y + j)$ are: $$ [7 \oplus 8, 7 \oplus 9, 7 \oplus 10, 8 \oplus 8, 8 \oplus 9, 8 \oplus 10, 9 \oplus 8, 9 \oplus 9, 9 \oplus 10] $$ which simplifies to $[15, 14, 13, 0, 1, 2, 1, 0, 3]$. The set of distinct values is $S(7, 8, 3) = \{0, 1, 2, 3, 13, 14, 15\}$, so the size is $7$. It can be shown that no other $y$ yields a larger size. However, the choice of $y$ matters; for example, if you chose $y = 22$, you would get $S(7, 22, 3) = \{16, 17, 30, 31\}$ with size $4$, which is suboptimal.

In the sixth example, after countless calculations, we managed to figure out that the optimal $y$ is $278\,302\,368\,699\,121\,665$, which gives an answer of $398\,158\,383\,604\,301\,822$. The proof is left to the reader as a trivial exercise.