给定一个数组 $A$，你可以执行零次或多次以下操作：

• 选择一个下标 $i$ ($1 \le i \le |A|$)，使得 $A_i = i$，并从数组 $A$ 中删除第 $i$ 个元素。
• 形式化地，将 $A$ 替换为 $A[1, i-1] + A[i+1, |A|]$，其中 $A[L, R]$ 表示子数组 $[A_L, A_{L+1}, A_{L+2}, \dots, A_R]$，而 $+$ 表示数组拼接。

令 $f(A)$ 表示在最优策略下应用操作后 $A$ 的最小可能长度。

给定整数 $N$ 和 $M$，求所有长度为 $N$ 且满足对于所有 $1 \le i \le N$ 都有 $1 \le A_i \le M$ 的 $M^N$ 个数组的 $f(A)$ 之和。由于答案可能很大，请输出其对 $998244353$ 取模的结果。

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例的第一行包含两个整数 $N$ 和 $M$。

输出格式

对于每个测试用例，输出一行，表示所有长度为 $N$ 且元素范围在 $M$ 以内的数组的 $f(A)$ 之和，对 $998244353$ 取模。

数据范围

• $1 \le T \le 10$
• $1 \le N, M < 998244353$
• $|N - M| \le 2000$

样例

样例输入 1

9
2 2
2 1
3 1
3 2
3 3
3 5
6 3
23 10
900000000 900000000

样例输出 1

3
0
0
9
44
284
2534
243195864
193285282

说明 1

测试用例 1：共有 $2^2 = 4$ 个可能的数组。它们各自的值为：

• $f([1, 1]) = 0$。首先应用 $i = 1$ 的操作。然后 $A$ 变为 $[1]$，我们可以再次应用 $i = 1$ 的操作，得到空数组。
• $f([1, 2]) = 0$。首先应用 $i = 2$ 的操作，然后应用 $i = 1$ 的操作。
• $f([2, 1]) = 2$。无法进行任何操作。
• $f([2, 2]) = 1$。应用 $i = 2$ 的操作。

总和为 $3$。