I. Fake Walsh Transform
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a set of integer $$$\{0,1,2,\ldots, 2^m-1\}$$$. Now you need to select $$$k$$$ integers from the set. Each integer should be selected no more than once. Let's denote the integers you selected by $$$a_1,a_2,\ldots, a_k$$$. You should make sure that $$$a_1\oplus a_2\oplus \ldots \oplus a_k=n$$$, where $$$\oplus$$$ indicates the bitwise exclusive OR operation.

You want to make $$$k$$$ as large as possible. Please calculate the maximum $$$k$$$.

Input

The first line contains one integer $$$T$$$ ($$$1\le T\le 10^4$$$), indicating the number of test cases.

For each test case, the only line contains two integers $$$m$$$ and $$$n$$$ ($$$1\le m\le 60$$$, $$$0\le n \lt 2^m$$$).

Output

For each test case, output one integer in a single line, indicating the maximum $$$k$$$.

Example
Input
1
2 2
Output
3
Note

For example, we can select $$$\{0,1,3\}$$$ from the set, since $$$0\oplus1\oplus3=2$$$.