A - Finding (((...))) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

整数 N,K が与えられます．

(,) からなる正しい括弧列 s に対し，そのスコアを次のように定義します．

  • (( \times c )+ ( ) \times c) という形の文字列 ((), (()), ((())), etc...) をよい文字列と呼ぶことにする． s に(連続するとは限らない)部分列として含まれるよい文字列の長さの最大値を，s のスコアとする．

長さ 2N の正しい括弧列であって，スコアがちょうど 2K になるものの個数を 998244353 で割ったあまりを求めてください．

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

正しい括弧列とは 正しい括弧列とは、() である部分文字列を削除することを 0 回以上繰り返して空文字列にできる文字列を指します。

制約

  • 1 \leq T \leq 10^5
  • 1 \leq K \leq N \leq 10^6
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

T
case_1
case_2
\vdots
case_T

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

N K

出力

答えを出力せよ．

入力例 1

4
2 1
2 2
3 1
100 70

出力例 1

1
1
0
366458221

長さ 4 の正しい括弧列と，そのスコアは以下のとおりです．

  • ()(): スコア 2
  • (()): スコア 4