問題文

$N$ 個の水晶が一列に並んでいます。しかし、中には実体のない幻影が含まれている可能性があります。

Junは、全ての $l,r (1 \le l \le r \le N)$ の組について、$l$ 番目から $r$ 番目まで(閉区間)に含まれる実体のある水晶の個数を数え、その偶奇を記録しました。

彼の $\frac{N(N+1)}{2}$ 個の記録によると、実体が奇数個含まれる区間は $K$ 個でした。このとき、水晶の並び方として考えられるものはいくつありますか？ 答えを$998244353$で割ったあまりを求めてください。

ただし、ある $i$ において一方では左から$i$番目の水晶に実体があり、もう一方では実体がない場合に、２つの並び方を異なるとみなします。

以上の問題が $T$ 個与えられます。それぞれに答えてください。

入力

$T$
$N_1\ K_1$
$\vdots$
$N_T\ K_T$

• 入力は全て整数
• $1 \le T \le 10^5$
• $1 \le N_i \le 10^5$
• $0 \le K_i \le \frac{N_i(N_i+1)}{2}$

出力

$T$ 行出力してください。$i$ 行目には、$N = N_i, K = K_i$ としたときの問題の答えを出力してください。
各行末は改行してください。

サンプル

1
3 4

3

5
5 9
6 10
10 24
10 25
100000 75915540

10
21
165
0
651081880