VegiCat gefur þér tvær heiltölur $n$ og $m$. Lítum á heiltölufylki $a_1, a_2, \ldots, a_n$ þannig að

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

Látum $s_i = a_1 + a_2 + \ldots + a_i$ vera forskeytissummur $a$. VegiCat segir þér einnig forskeytissummurnar í $m$ sætum; það er að segja, þér eru gefin $m$ skilyrði á forminu $s_{p_j} = v_j$ ($1 \le j \le m$).

Teljið fjölda fylkja sem uppfylla öll skilyrðin, módulo $998\,244\,353$. Ef ekkert fylki uppfyllir öll skilyrðin er svarið $0$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir á eftir.

Hvert prófunartilvik er gefið sem hér segir:

Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($1 \le n \le 100$, $0 \le m \le n$), lengd fylkisins og fjölda skilyrða á forskeytissummur, í þessari röð.

Sú $j$-ta af næstu $m$ línum inniheldur tvær heiltölur $p_j$ og $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Þetta lýsir skilyrði: summa fyrstu $p_j$ stakanna í fylkinu verður að vera jöfn $v_j$.

Sætin $p_j$ eru gefin í strangt vaxandi röð.

Úttak

Fyrir hvert prófunartilvik skal prenta heiltölu — fjölda gildra fylkja módulo $998\,244\,353$.

Dæmi

Inntak 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

Úttak 1

1
1
2
2
2
0

Skýring

Án nokkurra forskeytisskilyrða eru nákvæmlega $2^{n-1}$ slík fylki, vegna þess að hver af $n - 1$ mismunum aðliggjandi staka getur óháð hinum verið $0$ eða $1$.

Í öðru prófunartilvikinu er eina fylkið með $s_3 = 1$ fylkið $(0, 0, 1)$.

Í þriðja prófunartilvikinu neyðir $s_2 = 0$ fram $a_2 = 0$, og eftir það getur $a_3$ verið $0$ eða $1$.

Í fjórða prófunartilvikinu eru fylkin $(0, 1, 1, 1)$ og $(0, 0, 1, 2)$.

Í fimmta prófunartilvikinu eru fylkin með $s_5 = 4$ fylkin $(0, 0, 1, 1, 2)$ og $(0, 1, 1, 1, 1)$.

Í sjötta prófunartilvikinu neyðir $s_2 = 0$ fram $a_1 = a_2 = 0$, þannig að $s_5 \le 6$. Skilyrðið $s_5 = 10$ er ómögulegt.