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$ 係冇可能滿足嘅。