Problem L
Limbo: Part 1

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 notes that when using dream-sharing technology, time slows down by different factors depending on whose dream is being entered. Their target is to convince Cepshun, the heir of an energy conglomerate, to dissolve his father’s company. Before Cobb starts, he notes that it would be important to figure out the passage of time to ensure that the operation can be completed smoothly.

In Cepshun’s dreams, there are multiple different layers of consciousness, each of which controls a different area of Cepshun’s dreams and memories. Cobb needs to move between several dreams to reach his destination dream – some of them belonging to Cepshun, and some of them belonging to his entourage. The factor by which time slows down on each level is best visualized by all of the positive integers arranged in an infinite triangle, where the first row has the single integer $1$, the second row has the next two integers, the third row has the next three, and so forth. The first $4$ levels are depicted below:

      1
     2 3
    4 5 6
   7 8 9 10
    etc...

The initial time factor for reality is $1$. To enter the next dream level, Cobb can either descend left (into a dream by Cepshun) or right (into a dream by his entourage). For example, if he descends right, left, right, then he’ll end up at dreams with time factors of $3$, then $5$, and finally $9$. Note the interesting property that for any pair of whole numbers $L$ and $R$, Cobb will always end up on the same time factor if he moves left $L$ times total and right $R$ times total, regardless of the order in which he makes the moves.

Cobb wants to know the slowness of time inside his target dream, which he can reach by descending left $L$ times and right $R$ times.

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, $L$ and $R$ ($0 \leq L, R \leq 10^{9}$), specifying the number of times Cobb needs to descend left and right, respectively.

Output

For each test case, print, on a separate line, the factor by which time slows down in the target’s dream at $(L, R)$.
Note: the answer can be large, and may not necessarily fit in a 32-bit integer.

3
1 2
2 3
5 8

9
19
100