E. What Does Geo Do In His Free Time
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Suppose you have a collection of $$$n$$$ dice, each with $$$k$$$ sides, numbered $$$1$$$ through $$$k$$$.

Or why would you suppose!!!, I will tell you what $$$\textit{Geo-Ghaffar}$$$ does in his free time and you imagine with me.

$$$\textit{Geo-Ghaffar}$$$ has a collection of $$$n$$$ dice, each with $$$k$$$ sides (numbered $$$1$$$ through $$$k$$$). When he is bored he plays the following game:

At each turn, he throws all the dice, chooses a number $$$x$$$ between $$$1$$$ and $$$k$$$ (inclusive) and discards all dice that show $$$x$$$ on their top face. He keeps doing this until He has no dice left.

Now $$$\textit{Geo-Ghaffar}$$$ is wondering that if the dice are fair, so each possible $$$\textbf{arrangement}$$$ of numbers on the dice is $$$\textbf{equally likely}$$$, What is the expected number of turns it will take to finish the game if he plays optimally. meaning he always choose the number $$$x$$$ that maximizes the number of dice that will be removed on that turn.

Since the answer may be large, print it modulo $$$998244353$$$.

Can you help him find the answer?

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 5)$$$ — the number of test cases. The descriptions of the test cases follow.

The only line of each testcase contains two integers $$$n,k$$$ $$$(1 \le k \le n \le 700)$$$.

The sum of $$$n$$$ over testcases does not exceed $$$700$$$.

Output

For each test case, output one integer: The expected number of turns it will take to finish the game if $$$\textit{Geo-Ghaffar}$$$ plays optimally — modulo $$$998244353$$$.

Examples
Input
2
2 2
3 3
Output
332748119
249561090
Input
1
2 2
Output
332748119
Note

Explanation: $$$\textit{Geo-Ghaffar}$$$ has two dice, each will show either $$$1$$$ or $$$2$$$. The possible arrangements are:

-$$$[1,1]$$$ and he can exclude $$$1$$$ and take one turn to finish.

-$$$[1,2]$$$ and he can exclude $$$1$$$, then there will be one die no matter what it will show it takes one turn to be discarded, so this takes two turns to finish.

-$$$[2,2]$$$ and he can exclude $$$2$$$ and take one turn to finish.

each has probability $$$\frac{1}{3}$$$, so the answer is $$$\frac{1+2+1}{3}=\frac{4}{3}$$$

Note that $$$[1,2]$$$ and $$$[2,1]$$$ are equivalent.