Little Cyan Fish は再び順列を数えています。

Little Cyan Fish は 3 つの整数 $n$、$k$、$S$ を持っています。長さ $n$ の順列とは、$1$ から $n$ までの各整数をちょうど 1 回ずつ含む数列のことです。Little Cyan Fish は、添字 $i$ が $1 \le i \le n - 2$ かつ $p_i + p_{i+1} \le S$ を満たすとき、その添字を良い添字と呼びます。

ちょうど $k$ 個の良い添字を持つ長さ $n$ の順列 $p$ の個数を求めてください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す単一の整数 $T$（$1 \le T \le 1000$）が含まれます。

各テストケースについて、1 行目には 3 つの整数 $n$、$k$、$S$（$1 \le k \le n \le 10^5$、$1 \le S \le 2n - 1$）が含まれます。

すべてのテストケースにおける $n$ の総和は $10^5$ を超えないことが保証されています。

出力

各テストケースについて、ちょうど $k$ 個の良い添字を持つ順列の個数を $998\,244\,353$ で割った余りを表す単一の整数を 1 行に出力してください。

入出力例

入力 1

6
3 1 3
3 1 4
4 1 4
4 2 5
3 2 5
1 1 1

出力 1

2
4
12
10
0
0

注記

1 番目のテストケースでは、条件を満たす 2 つの順列は $[1, 2, 3]$ と $[2, 1, 3]$ です。

2 番目のテストケースでは、条件を満たす 4 つの順列は $[1, 2, 3]$、$[2, 1, 3]$、$[1, 3, 2]$、$[3, 1, 2]$ です。

5 番目と 6 番目のテストケースでは、$1 \le i \le n - 2$ を満たす添字が $k$ 個未満であるため、答えは $0$ です。