说明

给定整数 $N$ 和 $K$。对于一个正整数 $k$，定义 $f(k)$ 如下：

• 对所有满足条件 $N \ge a_1 \ge a_2 \ge \ldots \ge a_k \ge 0$ 的整数序列 $(a_1, a_2, \ldots, a_k)$，求 $\binom{N}{a_1} \times \binom{a_1}{a_2} \times \cdots \times \binom{a_{k-1}}{a_k}$ 的和。

请求出 $\sum_{k=1}^{K} f(k)$ 除以 $998244353$ 的余数。

对于每组输入，你需要解决 $T$ 个测试用例。

注意，$\binom{A}{B}$ 表示“从 $A$ 个物品中选取 $B$ 个不同物品的方案数”（即组合数）。

输入格式

$$\begin{aligned} & T \\ & \text{case}_1 \\ & \vdots \\ & \text{case}_T \end{aligned}$$

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

$$N \quad K$$

输入满足以下约束：

• 所有测试用例均由整数构成。
• $1 \le T \le 10^5$
• $0 \le N \le 10^9$
• $1 \le K \le 2 \times 10^5$
• 单个测试文件中所有测试用例的 $K$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出 $\sum_{k=1}^{K} f(k)$ 除以 $998244353$ 的余数。

3
3 3
0 1
31415 92653

99
1
276482222

提示

翻译由 DeepSeek V3.2 完成