Little Cyan Fish sta contando di nuovo le permutazioni.

Little Cyan Fish ha tre interi $n$, $k$ e $S$. Una permutazione di lunghezza $n$ è una sequenza che contiene ogni intero da $1$ a $n$ esattamente una volta. Little Cyan Fish chiama buono un indice $i$ se $1 \le i \le n - 2$ e $p_i + p_{i+1} \le S$.

Trova il numero di permutazioni $p$ di lunghezza $n$ che hanno esattamente $k$ indici buoni. Poiché la risposta può essere grande, stampala modulo $998\,244\,353$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 1000$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene tre interi $n$, $k$ e $S$ ($1 \le k \le n \le 10^5$, $1 \le S \le 2n - 1$).

È garantito che la somma di $n$ su tutti i casi di test non superi $10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente un singolo intero, che indica il numero di permutazioni che hanno esattamente $k$ indici buoni, modulo $998\,244\,353$.

Esempi

Input 1

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

Output 1

2
4
12
10
0
0

Nota

Nel primo caso di test, le due permutazioni sono $[1, 2, 3]$ e $[2, 1, 3]$.

Nel secondo caso di test, le quattro permutazioni sono $[1, 2, 3]$, $[2, 1, 3]$, $[1, 3, 2]$ e $[3, 1, 2]$.

Nel quinto e nel sesto caso di test, ci sono meno di $k$ indici che soddisfano $1 \le i \le n - 2$, quindi la risposta è $0$.