给定整数 $n$ 和 $k$。

对于正整数 $q$，$f(q)$ 定义为满足条件 $n \ge a_1 \ge a_2 \ge \dots \ge a_q \ge 0$ 的所有整数序列 $(a_1, a_2, \dots, a_q)$ 的以下乘积之和： $$\binom{n}{a_1} \cdot \binom{a_1}{a_2} \cdot \dots \cdot \binom{a_{q-1}}{a_q}$$

计算 $\sum_{q=1}^{k} f(q)$ 对 $998\,244\,353$ 取模的结果。

此处 $\binom{A}{B}$ 为二项式系数：从 $A$ 个不同元素中选取 $B$ 个不同元素的方法数。

输入格式

第一行包含一个整数 $t$：测试用例的数量 ($1 \le t \le 10^5$)。 接下来的 $t$ 行，每行包含两个整数：$n$ 和 $k$ ($0 \le n \le 10^9$; $1 \le k \le 2 \cdot 10^5$)。 所有测试用例中 $k$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出该和对 $998\,244\,353$ 取模的结果。

样例

输入 1

4
2 2
0 1
271 818
141 42

输出 1

13
1
812506614
405709861