VegiCat 給你兩個整數 $n$ 和 $m$。考慮滿足以下條件的整數陣列 $a_1, a_2, \ldots, a_n$：

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

設 $s_i = a_1 + a_2 + \ldots + a_i$ 為 $a$ 的前綴和。VegiCat 還告訴了你 $m$ 個位置上的前綴和；也就是說，給定 $m$ 條形如 $s_{p_j} = v_j$（$1 \le j \le m$）的限制。

求滿足所有限制的陣列數量，對 $998\,244\,353$ 取模。如果沒有陣列滿足所有限制，則答案為 $0$。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 10^4$），表示測試資料的數量。接下來是各組測試資料的描述。

每組測試資料的格式如下：

第一行包含兩個整數 $n$ 和 $m$（$1 \le n \le 100$，$0 \le m \le n$），分別表示陣列的長度和前綴和限制的數量。

接下來 $m$ 行中的第 $j$ 行包含兩個整數 $p_j$ 和 $v_j$（$1 \le p_j \le n$，$0 \le v_j \le 10^9$）。這描述了一條限制：陣列前 $p_j$ 個元素之和必須等於 $v_j$。

位置 $p_j$ 按嚴格遞增順序給出。

輸出格式

對於每組測試資料，輸出一個整數——合法陣列的數量對 $998\,244\,353$ 取模的結果。

範例

輸入 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

輸出 1

1
1
2
2
2
0

說明

在沒有任何前綴和限制的情況下，恰好有 $2^{n-1}$ 個這樣的陣列，因為 $n - 1$ 個相鄰差分中的每一個都可以獨立地取 $0$ 或 $1$。

在第二組測試資料中，唯一滿足 $s_3 = 1$ 的陣列是 $(0, 0, 1)$。

在第三組測試資料中，$s_2 = 0$ 強制 $a_2 = 0$，此後 $a_3$ 可以是 $0$ 或 $1$。

在第四組測試資料中，符合條件的陣列為 $(0, 1, 1, 1)$ 和 $(0, 0, 1, 2)$。

在第五組測試資料中，滿足 $s_5 = 4$ 的陣列為 $(0, 0, 1, 1, 2)$ 和 $(0, 1, 1, 1, 1)$。

在第六組測試資料中，$s_2 = 0$ 強制 $a_1 = a_2 = 0$，因此 $s_5 \le 6$。限制 $s_5 = 10$ 是不可能滿足的。