VegiCat memberi Anda dua bilangan bulat $n$ dan $m$. Tinjau larik bilangan bulat $a_1, a_2, \ldots, a_n$ sedemikian sehingga

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

Misalkan $s_i = a_1 + a_2 + \ldots + a_i$ adalah jumlah prefiks dari $a$. VegiCat juga memberi tahu Anda jumlah prefiks pada $m$ posisi; artinya, Anda diberikan $m$ batasan berbentuk $s_{p_j} = v_j$ ($1 \le j \le m$).

Hitung banyaknya larik yang memenuhi semua batasan, modulo $998\,244\,353$. Jika tidak ada larik yang memenuhi semua batasan, jawabannya adalah $0$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yaitu banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul di bawahnya.

Setiap kasus uji diberikan sebagai berikut:

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 100$, $0 \le m \le n$), masing-masing menyatakan panjang larik dan banyaknya batasan jumlah prefiks.

Baris ke-$j$ dari $m$ baris berikutnya berisi dua bilangan bulat $p_j$ dan $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Ini mendeskripsikan sebuah batasan: jumlah dari $p_j$ elemen pertama larik harus sama dengan $v_j$.

Posisi $p_j$ diberikan dalam urutan menaik tegas.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat — banyaknya larik yang valid modulo $998\,244\,353$.

Contoh

Masukan 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

Keluaran 1

1
1
2
2
2
0

Catatan

Tanpa batasan prefiks apa pun, terdapat tepat $2^{n-1}$ larik seperti itu, karena masing-masing dari $n - 1$ selisih elemen bersebelahan dapat bernilai $0$ atau $1$ secara saling bebas.

Pada kasus uji kedua, satu-satunya larik dengan $s_3 = 1$ adalah $(0, 0, 1)$.

Pada kasus uji ketiga, $s_2 = 0$ memaksa $a_2 = 0$, yang setelahnya $a_3$ boleh bernilai $0$ atau $1$.

Pada kasus uji keempat, larik-lariknya adalah $(0, 1, 1, 1)$ dan $(0, 0, 1, 2)$.

Pada kasus uji kelima, larik-larik dengan $s_5 = 4$ adalah $(0, 0, 1, 1, 2)$ dan $(0, 1, 1, 1, 1)$.

Pada kasus uji keenam, $s_2 = 0$ memaksa $a_1 = a_2 = 0$, sehingga $s_5 \le 6$. Batasan $s_5 = 10$ tidak mungkin dipenuhi.