Description

ckw has many edge-cactus graphs. An edge-cactus graph is a simple undirected connected graph in which each edge belongs to at most one simple cycle.

ckw defines the degree sequence of an undirected graph. The length of the degree sequence is the number of vertices in the graph, and the $i$-th element of the degree sequence is the degree of the vertex numbered $i$.

ckw wants to know: among all edge-cactus graphs with $n$ vertices and $m$ edges, how many different degree sequences are there.

Output the answer modulo $998244353$. (If no valid cactus exists, output $0$.)

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, one line contains two integers $n, m$, representing the number of vertices and the number of edges.

Output Format

For each test case, output one integer per line, the answer modulo $998244353$.

7
4 4
5 6
50 70
90 102
40 41
2000 1999
1785 2425

13
5
442759796
851878741
292277388
943337434
183253103

Hint

[Sample Explanation]

For the first test case, here are four valid degree sequences: $\{2,2,2,2\},\{1,2,2,3\},\{1,2,3,2\},\{2,1,3,2\}$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (8 points): $n \le 5$.
• Subtask 2 (10 points): $n \le 10$.
• Subtask 3 (18 points): $n \le 35$.
• Subtask 4 (12 points): $n \le 90$.
• Subtask 5 (8 points): $m = n - 1$.
• Subtask 6 (10 points): $m = n$.
• Subtask 7 (16 points): $m = n + 1$.
• Subtask 8 (18 points): no special constraints.

For $100\%$ of the testdata, $1 \le T \le 10$, $0 \le n \le 2 \times 10^3$, $0 \le m \le 10^9$.

Translated by ChatGPT 5