有 $10^{100}$ 张牌，编号从 $1$ 到 $10^{100}$，堆叠在一起，使得第 $i$ 张牌是牌堆顶部的第 $i$ 张牌。 有一个空袋子。你将执行以下操作恰好 $M$ 次：

查看牌堆顶部的 $K$ 张牌，选择其中任意数量的牌（可能为零）放入袋子中。将未选择的牌按其原始相对顺序放回牌堆顶部。

在执行完所有 $M$ 次操作后，考虑袋子中可能出现的所有牌的集合。计算这些集合大小的总和，并将结果对 $998244353$ 取模。

给定 $T$ 组测试数据。对于每组测试数据，输出所需的值。

输入格式

输入格式如下：

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

每组测试数据格式如下：

$K \ M$

• 所有输入值均为整数。
• $1 \le T \le 10^5$
• $1 \le K < 998244353$
• $1 \le M < 998244353$

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试数据的答案。

样例

样例输入 1

3
2 1
3 2
20250308 410338673

样例输出 1

4
81
509595821

说明

在第一个样例中，袋子中可能的牌集合为 $\emptyset, \{1\}, \{2\}, \{1, 2\}$，它们的大小之和为 $4$。