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$ 個の位置における累積和を教えてくれます。すなわち、$s_{p_j} = v_j$（$1 \le j \le m$）という形の制約が $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

注記

累積和の制約が一つもない場合、$n - 1$ 個の隣接する差がそれぞれ独立に $0$ または $1$ をとり得るため、条件を満たす配列はちょうど $2^{n-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$ を満たすことは不可能です。