VegiCat daje ci dwie liczby całkowite $n$ oraz $m$. Rozważmy tablice liczb całkowitych $a_1, a_2, \ldots, a_n$ takie, że

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

Niech $s_i = a_1 + a_2 + \ldots + a_i$ oznacza sumy prefiksowe tablicy $a$. VegiCat podaje ci również sumy prefiksowe na $m$ pozycjach; to znaczy, otrzymujesz $m$ ograniczeń postaci $s_{p_j} = v_j$ ($1 \le j \le m$).

Policz liczbę tablic spełniających wszystkie ograniczenia, modulo $998\,244\,353$. Jeśli żadna tablica nie spełnia wszystkich ograniczeń, odpowiedzią jest $0$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych. Poniżej znajduje się opis przypadków testowych.

Każdy przypadek testowy podany jest w następujący sposób:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 100$, $0 \le m \le n$), oznaczające odpowiednio długość tablicy oraz liczbę ograniczeń na sumy prefiksowe.

$j$-ty z kolejnych $m$ wierszy zawiera dwie liczby całkowite $p_j$ oraz $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Opisuje to ograniczenie: suma pierwszych $p_j$ elementów tablicy musi być równa $v_j$.

Pozycje $p_j$ są podane w porządku ściśle rosnącym.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — liczbę poprawnych tablic modulo $998\,244\,353$.

Przykład

Wejście 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

Wyjście 1

1
1
2
2
2
0

Uwagi

Bez żadnych ograniczeń prefiksowych istnieje dokładnie $2^{n-1}$ takich tablic, ponieważ każda z $n - 1$ różnic sąsiednich elementów może niezależnie wynosić $0$ lub $1$.

W drugim przypadku testowym jedyną tablicą spełniającą $s_3 = 1$ jest $(0, 0, 1)$.

W trzecim przypadku testowym warunek $s_2 = 0$ wymusza $a_2 = 0$, po czym $a_3$ może wynosić $0$ lub $1$.

W czwartym przypadku testowym szukanymi tablicami są $(0, 1, 1, 1)$ oraz $(0, 0, 1, 2)$.

W piątym przypadku testowym tablicami spełniającymi $s_5 = 4$ są $(0, 0, 1, 1, 2)$ oraz $(0, 1, 1, 1, 1)$.

W szóstym przypadku testowym warunek $s_2 = 0$ wymusza $a_1 = a_2 = 0$, a więc $s_5 \le 6$. Ograniczenie $s_5 = 10$ jest niemożliwe do spełnienia.