Limbo: Part 2

Dominick Cobb and Arthur are “extractors" who perform corporate espionage. Using experimental military technology that gives them access to shared dream worlds, they infiltrate their targets’ subconscious to extract valuable information. Cobb and his entourage are contacted by a mysterious Japanese syndicate and given a seemingly impossible task: instead of extracting information, do the opposite – plant a new idea in the target’s mind.

Cobb just figured out how to calculate the slowness of time in each dream level, but he is still missing a vital piece of the plan – the architecture. For this challenging mission he has hired the brilliant young architect Ariadne to design a dream space, complete with all the aesthetic and tactile details. Cobb’s target will be brought into that dream space, where they will fill it with details from their own subconscious and memories.

As extractors go into deeper dream levels, the perception of time slows down. This means subjects will be able to explore exponentially more space. Since dreams can go infinitely deep (onwards to Limbo), the architecture of a dream should be infinite in area. The master layout is denoted by a two-dimensional grid that starts at row $0$, column $0$, and extends infinitely downwards and to the right. Ariadne cannot simply draw a map of this space (since it is infinite), so she must come up with a program that "generates" the dream space to extend as large as the team needs to go deeper. She has an infinite number of building blocks, numbered $0, 1, 2, 3, 4, \dots $, which must be used in that order.

In dream level $0$ (reality), the dream space consists of the single block $0$. With each deeper dream level, the area of the space doubles. To prevent the dream space from implosion due to growing too narrowly in a single direction, Ariadne has designed the space to double in alternating directions, with new blocks filling in the space sequentially based on the direction of doubling. For example, the first few levels of the dream map are depicted as follows:

    0          0 1         0 1       0 1 4 6
                           2 3       2 3 5 7

(Reality)   (Level 1)   (Level 2)   (Level 3)


   0  1  4  6         0  1  4  6 16 20 24 28
   2  3  5  7         2  3  5  7 17 21 25 29
   8  9 10 11         8  9 10 11 18 22 26 30
  12 13 14 15        12 13 14 15 19 23 27 31

   (Level 4)                (Level 5)

Ariadne’s program must be able to generate any part of the map at will. Given only the row and column coordinates for a particular location in the dream space, can you determine the number of the building block that will be used?

Input

The first line of input consists of a single integer $T$ ($1 \leq T \leq 100$), the number of test cases.
$T$ lines follow, each of which is a test case consisting of two space-separated integers, $R$ and $C$ ($0 \leq R, C \leq 10^{9}$), specifying a particular row and column in the dream-space.

Output

For each test case, print, on a separate line, the number of the building block at coordinates $(R, C)$.
Note: the answer can be large, and may not necessarily fit in a 32-bit integer.

Sample Input 1 Sample Output 1
3
0 0
1 0
2 4
0
2
18