409383: GYM103495 I Fake Walsh Transform

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$$$.

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 < 2^m$$$).

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

1
2 2

3

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