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$.

Найдите количество перестановок $p$ длины $n$, у которых ровно $k$ хороших индексов. Поскольку ответ может быть большим, выведите его по модулю $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]$.

В пятом и шестом наборах входных данных существует менее $k$ индексов, удовлетворяющих условию $1 \le i \le n - 2$, поэтому ответ равен $0$.