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 numbers
The corresponding decimal values are shown on the right.
These sequences are called Reflected Gray Codes for and bits respectively. A Gray Code for bits is a sequence of different -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 . Each test is a line with two integers: and .
For each test case, output the integer that appears in position of the -bit Reflected Gray Code.