問題文

1 から 10^{100} の番号がついた 10^{100} 枚のカードがあり、カード i が 上から i 番目になるように積まれています。 また、空の袋が 1 個あります。以下の操作をちょうど M 回行うことを考えます。

上から K 枚のカードを見て、カードを 0 枚以上好きな枚数選び、それらを袋に入れる。選ばれなかったカードは相対順序を保ったまま戻す。

操作終了後に袋に入っているカードの集合として考えられるもの全てに対する要素数の総和を 998244353 で割った余りを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力は全て整数
• 1 \leq T \leq 10^5
• 1 \leq K <998244353
• 1 \leq M < 998244353

入力例 1

3
2 1
3 2
20250308 410338673

出力例 1

4
81
509595821

1 番目のテストケースについて、袋の中に入ったカードの集合としてありうるものは \lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 2\rbrace, \lbrace 1,2 \rbrace で、要素数の総和は 4 です。