VegiCat gir deg to heltall $n$ og $m$. Betrakt heltallstabeller $a_1, a_2, \ldots, a_n$ slik at

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

La $s_i = a_1 + a_2 + \ldots + a_i$ være prefikssummene til $a$. VegiCat forteller deg også prefikssummene på $m$ posisjoner; det vil si at du får oppgitt $m$ betingelser på formen $s_{p_j} = v_j$ ($1 \le j \le m$).

Tell antallet tabeller som oppfyller alle betingelsene, modulo $998\,244\,353$. Hvis ingen tabell oppfyller alle betingelsene, er svaret $0$.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Hvert testtilfelle er gitt som følger:

Den første linjen inneholder to heltall $n$ og $m$ ($1 \le n \le 100$, $0 \le m \le n$), henholdsvis lengden på tabellen og antallet prefikssumbetingelser.

Den $j$-te av de neste $m$ linjene inneholder to heltall $p_j$ og $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Dette beskriver en betingelse: summen av de første $p_j$ elementene i tabellen må være lik $v_j$.

Posisjonene $p_j$ er gitt i strengt stigende rekkefølge.

Utdata

For hvert testtilfelle skal du skrive ut et heltall — antallet gyldige tabeller modulo $998\,244\,353$.

Eksempler

Inndata 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

Utdata 1

1
1
2
2
2
0

Forklaring

Uten noen prefiksbetingelser finnes det nøyaktig $2^{n-1}$ slike tabeller, fordi hver av de $n - 1$ nabodifferansene uavhengig kan være $0$ eller $1$.

I det andre testtilfellet er den eneste tabellen med $s_3 = 1$ lik $(0, 0, 1)$.

I det tredje testtilfellet tvinger $s_2 = 0$ fram $a_2 = 0$, og deretter kan $a_3$ være $0$ eller $1$.

I det fjerde testtilfellet er tabellene $(0, 1, 1, 1)$ og $(0, 0, 1, 2)$.

I det femte testtilfellet er tabellene med $s_5 = 4$ lik $(0, 0, 1, 1, 2)$ og $(0, 1, 1, 1, 1)$.

I det sjette testtilfellet tvinger $s_2 = 0$ fram $a_1 = a_2 = 0$, så $s_5 \le 6$. Betingelsen $s_5 = 10$ er umulig.