O. The Revolt of the Masked Guards
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Squid Game, the Masked Guards are responsible for maintaining order and eliminating rebellious Players. However, the Guards have secretly grown resentful of the system and wish to overthrow the Front Man. The Guards have discovered a key insight: if a group of consecutive Guards in the circular formation is surrounded by strictly more Players, they will be overpowered and eliminated.

For example, if the initial formation is: $$$$$$11000100101$$$$$$ where 1 represents a Player and 0 represents a Masked Guard, the Players can initially attack the first three Guards, as they are surrounded by 4 Players: $$$$$$110001∗∗∗∗1$$$$$$ leaving the new formation as: $$$$$$11100101$$$$$$ The process continues until the Players take control of the entire arena.

The Guards, realizing the imminent threat, decide to swap their positions in a circular manner, attempting to find an arrangement where, after all possible attacks, the number of remaining Guards is greater than or equal to the initial number of Players.

Your task is to determine how many different valid rearrangements of the Guards and Players exist to ensure that the Guards can survive the rebellion. As these numbers can be very large, print the result modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^6)$$$, representing the number of testcases.

For each testcase, you will be given two integers $$$k$$$ and $$$n$$$ $$$(1 \leq k \leq 10^6, 1 \leq n \leq 10^6)$$$, indicating the initial number of Players and the initial number of Guards.

Output

Print the answer modulo 998244353.

Example
Input
5
2 1
2 2
3 3
5 8
8 5
Output
0
16
216
204983294
0
Note

In the second test case if we enumerate the $$$4$$$ positions in the circular formation from $$$1$$$ to $$$4$$$ in clockwise order and we note the two players as $$$A$$$ and $$$B$$$ and the two guards as $$$C$$$ and $$$D$$$. Each permutation of this 4 letters represent a formation.

Then all possible valid rearrangements of the Guards and Players are : $$$ABCD$$$ , $$$BACD$$$ , $$$ABDC$$$ , $$$BADC$$$ , $$$CABD$$$ , $$$CBAD$$$ , $$$DABC$$$ , $$$DBAC$$$ , $$$CDAB$$$ , $$$CDBA$$$ , $$$DCAB$$$ , $$$DCBA$$$ , $$$ACDB$$$ , $$$ADCB$$$ , $$$BCDA$$$ , $$$BDCA$$$ so the answer is 16.