e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Gray codes

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

Output

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

Time limit 1 second
Memory limit 128 MiB
Input example #1
14
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
Output example #1
0
1
0
1
3
2
0
1
3
2
6
7
5
4