F. Modulo and Counting
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given two integers $$$n$$$ and $$$m$$$.

An array $$$a$$$ of length $$$n$$$ is called good if it satisfies the following two conditions:

  • $$$\color{red}{m + 2} \ge a_1 \ge a_2 \ge \ldots \ge a_{n-1} \ge a_n \ge 1$$$;
  • $$$(a_1 \bmod a_2) + (a_2 \bmod a_3) + \ldots + (a_{n-1} \bmod a_n) = m$$$.

Your task is to find the number of good arrays. Since the answer can be very large, report it modulo $$$998\,244\,353$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 2\,000$$$) — the number of test cases. The description of each test case follows.

The only line of each test case contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 4\,000$$$; $$$1 \le m \le 4\,000$$$).

It is guaranteed that the sum of $$$n$$$ over all the test cases does not exceed $$$4000$$$ and the sum of $$$m$$$ over all the test cases does not exceed $$$4000$$$.

Output

For each test case, print the number of good arrays. As the answer can be large, output it modulo $$$998\,244\,353$$$.

Example
Input
6
3 1
3 2
6 7
41 67
998 244
353 420
Output
3
1
60
972763487
288208692
566410295
Note

For the first test case, the good arrays are:

  • $$$[3, 2, 1]$$$: $$$(3 \bmod 2) + (2 \bmod 1) = 1 + 0 = 1$$$.
  • $$$[3, 2, 2]$$$: $$$(3 \bmod 2) + (2 \bmod 2) = 1 + 0 = 1$$$.
  • $$$[3, 3, 2]$$$: $$$(3 \bmod 3) + (3 \bmod 2) = 0 + 1 = 1$$$.

For the second test case, the only good array is $$$[4, 3, 2]$$$.