VegiCat ger dig två heltal $n$ och $m$. Betrakta heltalsfält $a_1, a_2, \ldots, a_n$ sådana att

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

Låt $s_i = a_1 + a_2 + \ldots + a_i$ vara prefixsummorna av $a$. VegiCat berättar också prefixsummorna på $m$ positioner; det vill säga, du får $m$ villkor på formen $s_{p_j} = v_j$ ($1 \le j \le m$).

Räkna antalet fält som uppfyller alla villkor, modulo $998\,244\,353$. Om inget fält uppfyller alla villkor är svaret $0$.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), antalet testfall. Beskrivningen av testfallen följer.

Varje testfall ges enligt följande:

Den första raden innehåller två heltal $n$ och $m$ ($1 \le n \le 100$, $0 \le m \le n$), fältets längd respektive antalet prefixsummevillkor.

Den $j$-te av de följande $m$ raderna innehåller två heltal $p_j$ och $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Detta beskriver ett villkor: summan av de första $p_j$ elementen i fältet måste vara lika med $v_j$.

Positionerna $p_j$ ges i strikt växande ordning.

Utdata

För varje testfall, skriv ut ett heltal — antalet giltiga fält modulo $998\,244\,353$.

Exempel

Indata 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

Förklaring

Utan några prefixvillkor finns det exakt $2^{n-1}$ sådana fält, eftersom var och en av de $n - 1$ intilliggande differenserna oberoende av varandra kan vara $0$ eller $1$.

I det andra testfallet är det enda fältet med $s_3 = 1$ lika med $(0, 0, 1)$.

I det tredje testfallet tvingar $s_2 = 0$ fram $a_2 = 0$, varefter $a_3$ kan vara $0$ eller $1$.

I det fjärde testfallet är fälten $(0, 1, 1, 1)$ och $(0, 0, 1, 2)$.

I det femte testfallet är fälten med $s_5 = 4$ lika med $(0, 0, 1, 1, 2)$ och $(0, 1, 1, 1, 1)$.

I det sjätte testfallet tvingar $s_2 = 0$ fram $a_1 = a_2 = 0$, så $s_5 \le 6$. Villkoret $s_5 = 10$ är omöjligt.