Mathison and the Dynamo shuffle `MATDYS`

All submissions for this problem are available.<h3>Read problems statements in mandarin chinese, russian and vietnamese as well.</h3>

Mathison has bought a new deck of cards that contains 2^N cards, numbered and ordered from 0 to 2^N-1.

Mathison is getting bored and decides to learn the Dynamo shuffle (or Sybil cut) - a flashy manner to shuffle cards. Unfortunately, the Dynamo shuffle is a little too complicated so Mathison decides to create his own shuffle.

This newly invented shuffle is done in N steps. At step k (0 ≤ k < N) the deck is divided into 2^k equal-sized decks where each one contains cards that lie on consecutive positions. Each one of those decks is then reordered: all the cards that lie on even positions are placed first followed by all cards that lie on odd positions (the order is preserved in each one of the two subsequences and all positions are 0-based). Then all the decks are put back together (preserving the order of decks).

Mathison has spent hours practising the shuffle and he now believes that he has perfected his technique. However, Chef doesn't believe him yet so he asks Mathison to answer Q questions that given a deck of size 2^N where i-th card is labelled i, find the position of the card labelled K in the final, shuffled deck.

Input

The first line of the input file will contain one integer, Q, representing the number of Chef's questions.

Each of the next Q lines will contain a pair of integers, N and K.

Output

The output file will contain Q lines, each one representing the answer to one of Chef's questions.

Constraints

1 ≤ Q ≤ 1000
1 ≤ N ≤ 64
0 ≤ K < 2^N

Subtaks

Subtask #1 (30 points):

1 ≤ N ≤ 10

Subtask #2 (30 points):

1 ≤ N ≤ 32

Subtask #3 (40 points):

Original constraints

Example

Input:
3
3 4
3 3
3 2

Output:
1
6
2

Input:
1
64 11047805202224836936

Output:
1337369305470044825

Explanation

In all questions, we have N = 3. Therefore, we have a deck with 8 cards.
The shuffling is done in three steps:

Step 0: We divide {0, 1, 2, 3, 4, 5, 6, 7} in 2⁰ decks. We get only one deck.
        The deck is reordered into {0, 2, 4, 6, 1, 3, 5, 7}.

Step 1: We divide {0, 2, 4, 6, 1, 3, 5, 7} in 2¹ decks. We get two decks: {0, 2, 4, 6} and {1, 3, 5, 7}.
        {0, 2, 4, 6} is reordered into {0, 4, 2, 6} while {1, 3, 5, 7} is reordered into {1, 5, 3, 7}.
        We get {0, 4, 2, 6, 1, 5, 3, 7} when we put the decks back together.

Step 2: We divide {0, 4, 2, 6, 1, 5, 3, 7} in 2² decks. We get four decks: {0, 4}, {2, 6}, {1, 5} and {3, 7}.
        Each one of the four decks stays the same after it is reordered (as there are only two elements to reorder).
        We get the final, shuffled deck: {0, 4, 2, 6, 1, 5, 3, 7}.

The card labelled 4 is on position 1.
The card labelled 3 is on position 6.
The card labelled 2 is on position 2.

Mathison and the Dynamo shuffle MATDYS