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.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 2 2 3 5 8 |
9 19 100 |
