Little Cyan Fish는 다시 순열을 세고 있습니다.

Little Cyan Fish에게는 세 정수 $n$, $k$, $S$가 있습니다. 길이가 $n$인 순열은 $1$부터 $n$까지의 각 정수를 정확히 한 번씩 포함하는 수열입니다. Little Cyan Fish는 인덱스 $i$가 $1 \le i \le n - 2$와 $p_i + p_{i+1} \le S$를 만족할 때, 그 인덱스를 좋은 인덱스라고 부릅니다.

정확히 $k$개의 좋은 인덱스를 가지는 길이가 $n$인 순열 $p$의 개수를 구하세요. 답이 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 출력하세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 단일 정수 $T$ ($1 \le T \le 1000$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 $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

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, 3]$과 $[2, 1, 3]$입니다.

두 번째 테스트 케이스에서 네 순열은 $[1, 2, 3]$, $[2, 1, 3]$, $[1, 3, 2]$, $[3, 1, 2]$입니다.

다섯 번째와 여섯 번째 테스트 케이스에서는 $1 \le i \le n - 2$를 만족하는 인덱스가 $k$개보다 적으므로, 답은 $0$입니다.