一个整数序列 $V_1, V_2, \dots, V_N$ 被称为超递减的，如果 $V_N \ge 0$，且对于所有 $1 \le i < N$，均满足 $V_i \ge V_{i+1} + V_{i+2} + \dots + V_N$。

给定正整数 $N$ 和 $M$，求满足以下条件的长度为 $N$ 的整数序列对 $(A, B)$ 的数量：对于所有 $1 \le i \le N$，均有 $1 \le A_i, B_i \le M$，且对于所有长度为 $N$ 的超递减序列 $V$，均满足：

$$\sum_{i=1}^N A_i V_i \ge \sum_{i=1}^N B_i V_i$$

由于满足条件的序列对数量可能非常大，请将答案对 $998\,244\,353$ 取模后输出。

输入格式

输入按以下格式给出：

T
N M
...

• 所有输入值均为整数。
• $1 \le T \le 100$
• $1 \le N, M \le 5000$
• 保证所有测试用例中 $N$ 的总和不超过 $5000$。
• 保证所有测试用例中 $M$ 的总和不超过 $5000$。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的序列对 $(A, B)$ 的数量对 $998\,244\,353$ 取模后的结果。

样例

输入样例 1

4
1 1
2 2
2 1
34 43

输出样例 1

1
10
1
711021868

说明

测试用例 1：唯一可能的序列对是 ($[1], [1]$)，且它是合法的。

测试用例 2：以下是合法的序列对：

• 对于 $B = [1, 1]$，任意 $A$ 的选择都是合法的。共有 $4$ 种可能的选择。
• 对于 $B = [1, 2]$，合法的 $A$ 选择为 $[1, 2], [2, 1], [2, 2]$。
• 对于 $B = [2, 1]$，合法的 $A$ 选择为 $[2, 1], [2, 2]$。
• 对于 $B = [2, 2]$，唯一合法的 $A$ 选择为 $[2, 2]$。

因此，合法的序列对数量为 $4 + 3 + 2 + 1 = 10$。