VegiCat ti dà due interi $n$ e $m$. Considera gli array di interi $a_1, a_2, \ldots, a_n$ tali che

$$ a_1 = 0, \qquad 0 \le a_{i+1} - a_i \le 1 \quad (1 \le i < n). $$

Sia $s_i = a_1 + a_2 + \ldots + a_i$ la somma prefissa di $a$. VegiCat ti comunica anche le somme prefisse in $m$ posizioni; cioè, ti vengono date $m$ restrizioni della forma $s_{p_j} = v_j$ ($1 \le j \le m$).

Conta il numero di array che soddisfano tutte le restrizioni, modulo $998\,244\,353$. Se nessun array soddisfa tutte le restrizioni, la risposta è $0$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di prova. Segue la descrizione dei casi di prova.

Ciascun caso di prova è fornito come segue:

La prima riga contiene due interi $n$ e $m$ ($1 \le n \le 100$, $0 \le m \le n$), rispettivamente la lunghezza dell'array e il numero di restrizioni sulle somme prefisse.

La $j$-esima delle successive $m$ righe contiene due interi $p_j$ e $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Questo descrive una restrizione: la somma dei primi $p_j$ elementi dell'array deve essere uguale a $v_j$.

Le posizioni $p_j$ sono date in ordine strettamente crescente.

Output

Per ciascun caso di prova, stampa un intero — il numero di array validi modulo $998\,244\,353$.

Esempi

Input 1

6
1 0
3 1
3 1
3 1
2 0
4 1
4 3
5 2
1 0
5 4
5 2
2 0
5 10

Output 1

1
1
2
2
2
0

Note

Senza alcuna restrizione sui prefissi ci sono esattamente $2^{n-1}$ array di questo tipo, perché ciascuna delle $n - 1$ differenze adiacenti può essere indipendentemente $0$ oppure $1$.

Nel secondo caso di prova, l'unico array con $s_3 = 1$ è $(0, 0, 1)$.

Nel terzo caso di prova, $s_2 = 0$ impone $a_2 = 0$, dopodiché $a_3$ può essere $0$ oppure $1$.

Nel quarto caso di prova, gli array sono $(0, 1, 1, 1)$ e $(0, 0, 1, 2)$.

Nel quinto caso di prova, gli array con $s_5 = 4$ sono $(0, 0, 1, 1, 2)$ e $(0, 1, 1, 1, 1)$.

Nel sesto caso di prova, $s_2 = 0$ impone $a_1 = a_2 = 0$, quindi $s_5 \le 6$. La restrizione $s_5 = 10$ è impossibile.