重复进行以下操作 $N$ 次：在 $0$ 到 $M-1$ 之间均匀随机选择一个整数。这些选择是相互独立的。

令 $A_i$ 为第 $i$ 次操作中选择的整数。计算 $\text{mex}(A_1, A_2, \dots, A_N)$ 的期望值，并将其对 $998244353$ 取模后输出。其中，$\text{mex}(A_1, A_2, \dots, A_N)$ 表示不在 $A_1, A_2, \dots, A_N$ 中的最小非负整数。

关于期望值对 $998244353$ 取模的定义：

可以证明本题所求的期望值总是一个有理数。此外，在本题的数据范围内，可以保证当所求期望值表示为最简分数 $\frac{y}{x}$ 时，$x$ 不能被 $998244353$ 整除。在这种情况下，存在唯一的 $0 \le z < 998244353$ 满足 $y \equiv xz \pmod{998244353}$，输出该 $z$ 即可。

输入格式

输入通过标准输入给出，格式如下：

$T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$

每个测试用例的格式如下：

$N \ M$

• $1 \le T \le 3 \times 10^5$
• $1 \le N, M \le 8000$
• 所有输入值均为整数。

输出格式

对于每个测试用例，输出一个整数，即该测试用例的答案对 $998244353$ 取模的结果。

样例

输入 1

4
3 2
1 1
20 23
8000 8000

输出 1

374341634
1
111675632
994279778

说明

在第一个测试用例中，可能的 $A$ 序列有 $(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0)$ 和 $(1, 1, 1)$。对应的 $\text{mex}$ 值分别为 $1, 2, 2, 2, 2, 2, 2$ 和 $0$。因此期望值为 $\frac{13}{8}$。