Mathison and the Dynamo shuffle

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
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} equalsized 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 0based). 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 ith 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^{0} 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^{1} 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^{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.
Author:  alexvaleanu 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/MATDYS 
Tags  alexvaleanu, easy, ltime51, observations 
Date Added:  15082017 
Time Limit:  0.5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 