問題文

整数 $N,K$ が与えられます。正整数 $k$ に対し、次の問題の答えを $f(k)$ とします。

• $N\geq a_1\geq a_2\geq \ldots \geq a_k \geq 0$ を満たす全ての整数列 $(a_1, a_2, \ldots, a_k)$ に対する $\displaystyle \binom{N}{a_1} \times \binom{a_1}{a_2} \times \cdots \times \binom{a_{k-1}}{a_k}$ の総和

$\displaystyle \sum_{k=1}^K f(k)$ を $998244353$ で割ったあまりを求めてください。

$1$ つの入力につき $T$ 個のテストケースについて解いてください。

ただし $\displaystyle \binom{A}{B}$ は「$A$ 個のものから $B$ 個のものを選び出す場合の数」（つまり二項係数）を表します。

制約

• 入力はすべて整数
• $1\leq T\leq 10^5$
• $0\leq N\leq 10^9$
• $1\leq K\leq 2\times 10^5$
• $1$ つの入力に含まれるテストケースについて、$K$ の総和は $2\times 10^5$ を超えない

入力

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

各テストケースは以下の形式で与えられる。

$N$ $K$

出力

サンプル

3
3 3
0 1
31415 92653

99
1
276482222