E. League of Legends
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

League of Legends (LoL), commonly referred to as League, is a 2009 multiplayer online battle arena video game developed and published by Riot Games. Inspired by Defense of the Ancients, a custom map for Warcraft III, Riot's founders sought to develop a stand-alone game in the same genre. Since its release in October 2009, League has been free-to-play and is monetized through purchasable character customization. The game is available for Microsoft Windows and macOS.

Eric and Clamee are playing Mundo Solo in Summon Canyon. Eric's Mundo has $$$n$$$ HP, while Clamee's Mundo has $$$m$$$ HP. The game ends when one's Mondo is reduced to $$$0$$$ HP. Eric is a Mondo grandmaster, so he will unleash Mondo's Q skill each turn. Clamee doesn't know how to play this game; hence, he will do nothing each turn. Mondo's skill is to cut himself by one HP, throw a dagger, and if it hits, cut the opponent by one HP. Eric's hit rate per Q skill is $$$\frac{1}{2}$$$.

Please find the probability that Eric's Mondo and Clamee's Mondo's HP will both go to 0 after a Q skill, computed modulo $$$998244353$$$.

Input

Each test consists of multiple test cases. The initial line presents a single integer $$$T~(1\le T\le 10^5)$$$ , which denotes the quantity of test cases.

In the context of each test instance, it contains one line presents two integers $$$n,m~(1\le n,m\le 10^6)$$$.

Output

For each test case, you are to output a single line containing the probability that Eric's Mondo and Clamee's Mondo's HP will both go to 0 after a Q skill, computed modulo $$$998244353$$$.

Example
Input
4
1 1
1 2
2 1
2 2
Output
499122177
0
748683265
748683265