# 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** (**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.

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

0 1 0 1 3 2 0 1 3 2 6 7 5 4