Gray codes#1519
We will generate a sequence of binary integers as follows.
Start with the sequence:
0
1
-Reflect this sequence with respect to a horizontal line: prefix each number in the first half with , and in the reflected (second) half with . The result is:
00
01
11
10Repeat this process to obtain a sequence of numbers:
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4The corresponding decimal values are shown on the right.
These sequences are called reflected Gray codes for n = 1, 2, 3. In general, a Gray code of length is a sequence of 2^n different -bit integers such that every two neighboring integers differ in exactly one bit. A reflected Gray code for bits is constructed as shown above.
The first line contains the number of test cases (1 \leq t \leq 250\,000). Each of the following lines contains two integers: (1 \leq n \leq 30) and (0 \leq k < 2^n).
For each test case, output the integer that appears at position in the sequence of -bit reflected Gray codes, each in a separate line.
Example 1