問題文

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

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

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

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

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

制約

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

入力例 1

4
2 1
2 2
3 1
100 70

出力例 1

1
1
0
366458221

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

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