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 flip | Alice | Bob | Outcome |
| 1st | 9$ | 2$ | heads |
| 2nd | 7$ | 4$ | heads |
| 3rd | 3$ | 8$ | tails |
| 4th | 6$ | 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.
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.
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$$$.
2 1 1 3 9
1 499122178
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$$$.
