We are going to generate a sequence of integers in binary. Start with the sequence
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
Repeat this again, and you will have 8 numbers
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.
The first line gives the number of test cases t (t≤250000). Each test is a line with two integers: n (1≤n≤30) and k (0≤k<2n).
For each test case, output the integer that appears in position k of the n-bit Reflected Gray Code.