E. Gambling
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice and Bob are compulsive gamblers. While waiting in the casino lobby, they started flipping coins for money (obviously), until one of them goes broke (obviously).

In the beginning, Alice has $$$a$$$ dollars and Bob has $$$b$$$ dollars. They flip a coin and if it lands on tails, Alice gets $$$\min(a,b)$$$ dollars from Bob; otherwise, Bob gets $$$\min(a,b)$$$ dollars from Alice. If one of them loses all the money, they stop and go to the closest ATM. Otherwise, they continue the same process.

For example, if Alice has (9$) and Bob has (2$) the process might go as follows:

Coin flipAliceBobOutcome
1st9$2$heads
2nd7$4$heads
3rd3$8$tails
4th6$5$tails

After the 4th coin flip, Bob has 0$ and they stop.

Some people in the lobby started making side bets on how many coin flips it will take before one of them goes broke. You also want to participate in the betting, but first, you have to compute the expected number of times they will flip a coin in the process, so you can make informed decisions.

Input

The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 100\,000$$$). The descriptions of the test cases follow.

The first and only line of a test case contains two integers $$$a,b$$$ ($$$1 \leq a,b \leq 10^{18}$$$) – the number of dollars that Alice and Bob have, respectively.

Output

We can prove that the sought expected value is always a finite rational number. Moreover, when the value is represented as an irreducible fraction $$$P/Q$$$, we can show that there exists a unique integer $$$R$$$ such that $$$R \cdot Q \equiv P \mod 998244353$$$ and $$$0\leq R \lt 998244353$$$.

For each test case print in a single line this integer $$$R$$$.

Example
Input
2
1 1
3 9
Output
1
499122178
Note

In the first test case, either Alice or Bob will lose all the money after the first coin flip.

In the second test case, the expected number of coin flips is $$$1 \frac{1}{2} \equiv 499122178 \mod 998244353$$$.