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

# 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
```