Problem I
Grey Codes
Input: Standard Input

Output: Standard Output

 

Gray hair is God's graffiti.

Bill Cosby

We are going to generate a sequence of integers in binary. Start with the sequence

0
1

 


Reflect it in the horizontal line, prepend 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
001
011
010
110
111
101
100

 

0
1
3
2
6
7
5
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 neighbouring integers differ in exactly one bit. A Reflected Gray Code is a Gray Code constructed in the way shown above.

 

Input

The first line of input gives the number of cases, N (at most 250000). N test cases follow. Each one 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.

 

 

 

 

Sample Input                                  Output for Sample Input

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
 

Problem setter: Igor Naverniouk