Gray codes

We are going to generate a sequence of integers in binary. Start with the sequence

0
1
-

Reflect it in the horizontal line, ascribe a zero to the numbers in the top half and a one to the numbers on the bottom and you will get

00
01
11
10

Repeat this again, and you will have $8$ numbers

000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4

The corresponding decimal values are shown on the right.

These sequences are called Reflected Gray Codes for $1,2$ and $3$ bits respectively. A Gray Code for $n$ bits is a sequence of $2n$ different $n$-bit integers with the property that every two neighboring integers differ in exactly one bit. A Reflected Gray Code is a Gray Code constructed in the way shown above.

Input

The first line gives the number of test cases $t(t\le 250000)$. Each test is a line with two integers: $n(1\le n\le 30)$ and $k(0\le k<2^n)$.

Output

For each test case, output the integer that appears in position $k$ of the $n$-bit Reflected Gray Code.

Examples