Problem K
Half-Grid Coverings

A half-grid is an $n$ by $n$ grid with everything above the main diagonal missing. For example, this is a half-grid of size $5$:


A covering of a half-grid of size $n$ is a partition of the half-grid into exactly $n$ non-overlapping rectangles. For example, here are two coverings of a half-grid of size $5$:


How many distinct coverings are there for a half-grid of size $n$, where all rectangles have area at most $k$? For example, for $n=5$ and $k=6$, the left covering above would be valid, because all rectangles have area at most $6$. However, the right covering above would not, because one rectangle has area $8$.

Two coverings are considered distinct if there exist two squares that are covered by the same rectangle in one covering, and different rectangles in the other.

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


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

Each test case consists of a single line with two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 10^6$) —the size of the half-grid and the maximum area of a rectangle in the covering, respectively.

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


For each test case, output a single integer —the number of coverings for a half-grid of size $n$, where all rectangles have an area of at most $k$, taken modulo $998244353$.

Sample Input 1 Sample Output 1
1 1
3 1
3 3
3 4
5 8
5 12345
18 50
18 999
400 1023
400 1000000

Please log in to submit a solution to this problem

Log in