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 n (at most 250000). Each test is a line with 2 integers: n (1 ≤ n ≤ 30) and k (0 ≤ k < 2n).

Output

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