the-magician-17

Robert Angier is divising a new magic trick to beat his rival Alfred Borden. He is going to perform a card trick. In this trick, cards are numbered from 1 to N. This trick involves the following process. Angier will invite a person from audience to shuffle the cards in random order.     

Following is defined as a single move:     
He will take a card from top of the deck, place card facing downwards on a table. Again he will take a card from top of the deck and place it below the deck. For example if current deck is suppose ABCDE, after one move A will be on the table (facing downwards) and the state of deck will be CDEB.     

Angier after taking the random shuffled deck, will perform the above move many times until only one card is left. After only one card is left, he will put that card also on the table. Now Angier will turn all the cards present on the table so that number on them is visible. To astonishment of everyone the cards are numbered in sequence from 1 to N.       

To perform this trick, Angier will put his assistant among the audience, who will arrange the cards into the required order. For example, let us suppose the deck was of size 6 and all cards were numbered from 1 to 6. His assistant will arrange the deck into 1,4,2,6,3,5. The moves when applied onto such a deck will result in 1,2,3,4,5,6. You need to tell to his assistant at what position should the card numbered K should be placed.       

For example in the above case where N=6, if K=6, the answer will be 4 since card numbered 6 is placed at 4th position.        

Input Format 
First line contains T, the number of testcases. Each testcase consists of two space seperated integers denoting N and K.       

Output Format 
For each testcase, print in one line, the required answer.           

Constraints 
1 ≤ T ≤ 100  
1 ≤ N ≤ 10^9 
1 ≤ K ≤ N

SAMPLE INPUT
1
6 6

SAMPLE OUTPUT
4

Source: hackerearth | Difficulty: HARD
Tags: Mathematics


Solutions: