Nell'algoritmo KMP, l'array next (noto anche come array LPS, per Longest Prefix Suffix, o funzione di fallimento) è un concetto fondamentale. Data una stringa $S = s_1s_2\dots s_n$ di lunghezza $n$, il suo array next $next[1..n]$ è definito in modo tale che $next[i]$ rappresenti la lunghezza del più lungo prefisso proprio e suffisso proprio uguali della sottostringa $S[1..i]$; nello specifico, $next[1] = 0$. Formalmente, è definito come:

$$next[i] = \max_{k=0,\dots,i-1} \{k : S[1\dots k] = S[i-k+1\dots i]\}$$

Qui, $S[l..r]$ è definita come la sottostringa formata dall'$l$-esimo carattere all'$r$-esimo carattere della stringa $S$. Si considera che $\forall 1 \le i \le n$, $S[1\dots 0] = S[i+1\dots i]$, entrambe stringhe vuote.

Dato un array $A[1..n]$ di lunghezza $n$, devi contare quante diverse stringhe $S$ di lunghezza $n$ definite sull'alfabeto $\Sigma$ hanno un array next esattamente uguale all'array dato $A$. La dimensione dell'alfabeto è $m$. Stampa il numero di tali stringhe modulo $998\,244\,353$.

Input

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

Per ciascun caso di test:

• La prima riga contiene due interi $n$ ($2 \le n \le 10^5$) e $m$ ($1 \le m \le 10^6$) che rappresentano la lunghezza dell'array dato e la dimensione dell'alfabeto.
• La seconda riga contiene $n$ interi separati da spazi, che rappresentano l'array dato $A$. È garantito che $\forall 1 \le i \le n$, $0 \le A_i \le i - 1$.

È garantito che la somma totale di $n$ non superi $5 \times 10^5$, ovvero $\sum n \le 5 \times 10^5$.

Output

Per ciascun caso di test, stampa una singola riga con un singolo intero, che rappresenta il numero di stringhe che soddisfano le condizioni, con la risposta calcolata modulo $998\,244\,353$.

Esempio

Input

3
3 3
0 1 2
7 3
0 0 0 1 2 3 0
7 3
0 0 0 1 2 3 1

Output

3
24
0

Note

Per il secondo gruppo di dati nell'esempio, supponiamo che l'alfabeto sia $\Sigma = \{'a', 'b', 'c'\}$. Le $24$ stringhe che soddisfano i requisiti sono:

abbabbb abbabbc abcabcb abcabcc acbacbb acbacbc
accaccb accaccc baabaaa baabaac bacbaca bacbacc
bcabcaa bcabcac bccbcca bccbccc caacaaa caacaab
cabcaba cabcabb cbacbaa cbacbab cbbcbba cbbcbbb