Rilly 想要送给 Northy 一些糖葫芦作为生日礼物。他买了 $n$ 个不同的山楂果和 $m$ 根不同的竹签来制作糖葫芦。

首先，Rilly 将山楂果从 $1$ 到 $n$ 进行编号。他对糖葫芦有着独特的偏好：对于在一串糖葫芦上相邻的两个编号为 $i$ 和 $j$ 的山楂果，所有编号介于 $i$ 和 $j$ 之间的山楂果必须与它们在同一串糖葫芦上，并且必须排在它们上方。

例如，$[2, 3, 1, 4]$（从上到下排列）是一串糖葫芦上山楂果的有效排列，因为：

• 在 $3$ 和 $1$ 之间的数是 $\{2\}$，且 $2$ 在 $3$ 和 $1$ 的上方；
• 在 $1$ 和 $4$ 之间的数是 $\{2, 3\}$，显然它们都在 $1$ 和 $4$ 的上方。

$[1, 4]$ 是无效的，因为 $\{2, 3\}$ 不在这串糖葫芦上。

$[1, 4, 2, 3]$ 也是无效的，因为 $3$ 介于 $4$ 和 $2$ 之间，但它被排在了它们的下方。

假设所有 $n$ 个山楂果和 $m$ 根竹签都必须被使用，且每串糖葫芦都不能为空。请计算有多少种制作糖葫芦的有效方案。两种方案不同，当且仅当存在某根竹签上穿的山楂果序列不同。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^6$），表示测试用例的数量。

接下来 $T$ 行，每行包含两个整数 $n, m$（$1 \le n \le 10^9, 1 \le m \le 10^6$），分别表示山楂果的数量和竹签的数量。

保证 $\sum m \le 10^6$。

输出格式

输出一个整数，表示答案对 $998244353$ 取模后的结果。

样例

输入样例 1

1
4 2

输出样例 1

24

说明

有效的方案为：

[1] , [2, 3, 4]    [2, 3, 4] , [1]    [1] , [3, 2, 4]    [3, 2, 4] , [1]
[1] , [3, 4, 2]    [3, 4, 2] , [1]    [1] , [4, 3, 2]    [4, 3, 2] , [1]
[1, 2] , [3, 4]    [3, 4] , [1, 2]    [1, 2] , [4, 3]    [4, 3] , [1, 2]
[2, 1] , [3, 4]    [3, 4] , [2, 1]    [2, 1] , [4, 3]    [4, 3] , [2, 1]
[1, 2, 3] , [4]    [4] , [1, 2, 3]    [2, 1, 3] , [4]    [4] , [2, 1, 3]
[2, 3, 1] , [4]    [4] , [2, 3, 1]    [3, 2, 1] , [4]    [4] , [3, 2, 1]