A. Safety First
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A ladder has $$$n$$$ sections, each of which has a positive integer length, and the lengths are sequentially non-increasing. That is, the lengths of these $$$n$$$ sections from left to right $$$d_1, d_2, \ldots, d_n$$$ should satisfy $$$d_1 \ge d_2 \ge \cdots \ge d_n$$$.

Little Q needs a ladder that, when stood upright, has a height exactly equal to $$$m$$$, where the height of a ladder is defined as the altitude difference between its highest end and its lowest end. For safety reasons, this ladder needs to be stable, which means it satisfies the following requirements:

  • The lower end of the first section of the ladder must touch the ground;
  • For each $$$i=1,2,\ldots,n-1$$$, the upper end of the $$$i$$$-th section must be locked into either the upper end or the lower end of the $$$(i+1)$$$-th section.

You need to compute the number of different stable ladders with $$$n$$$ sections that can be constructed if their height when stood upright is exactly $$$m$$$. Two ladders are considered different if and only if there exists some $$$k$$$ such that the lengths of the $$$k$$$-th section of the two ladders are different, or if the $$$k$$$-th section of one ladder is locked into the upper end of the $$$(k+1)$$$-th section while the $$$k$$$-th section of the other ladder is locked into the lower end of the $$$(k+1)$$$-th section.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$), indicating the number of test cases. For each test case:

The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2\,000$$$), indicating the number of sections and the required height of the stable ladder.

Output

For each test case, output a line containing an integer, indicating the number of different stable ladders modulo $$$998\,244\,353$$$.

Examples
Input
3
1 3
2 3
3 3
Output
1
4
10
Input
1
2000 2000
Output
204576309
Note

In the following explanation, we use bold text to indicate that the upper end of the corresponding section is locked into the lower bound of the next section and keep the same in other scenarios.

In the first sample case:

  • for the first test case, the only possible ladder has a single section of length $$$1$$$;
  • for the second test case, the section lengths of all $$$4$$$ possible ladders are $$$[\textbf{2}, 1]$$$, $$$[3, 1]$$$, $$$[3, 2]$$$ and $$$[3, 3]$$$ respectively;
  • for the third test case, the section lengths of all $$$10$$$ possible ladders are $$$[\textbf{1}, \textbf{1}, 1]$$$, $$$[\textbf{2}, 1, 1]$$$, $$$[2, \textbf{1}, 1]$$$, $$$[2, \textbf{2}, 1]$$$, $$$[3, 1, 1]$$$, $$$[3, 2, 1]$$$, $$$[3, 2, 2]$$$, $$$[3, 3, 1]$$$, $$$[3, 3, 2]$$$ and $$$[3, 3, 3]$$$ respectively.