Little Cyan Fish は合計 $n$ 個の整数からなる $m$ 個の数列を持っています。$1$ から $n$ までの各整数は、すべての数列を通してちょうど 1 回ずつ現れます。

彼はこれらの数列をマージして、長さ $n$ の順列 $p$ を作りたいと考えています。最初、$p$ は空です。各ステップにおいて、彼は空でない数列を 1 つ選び、その先頭の整数を取り除き、その整数を $p$ の末尾に追加します。すべての数列が空になるまでこれを繰り返します。

順列 $p$ 内の整数について、その値が $p$ における位置と等しいとき、その整数を $p$ の不動点と呼びます。位置は $1$ から $n$ まで番号付けられます。

$p$ に含まれる不動点の個数の最小値を求めてください。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す単一の整数 $T$（$1 \le T \le 10^6$）が与えられます。

各テストケースについて、1 行目には 2 つの整数 $n$ と $m$（$1 \le m \le n \le 10^6$）が与えられ、それぞれ整数の総数と数列の個数を表します。

続く $m$ 行には各数列の情報が与えられます。このうち $i$ 行目には整数 $k_i$（$1 \le k_i \le n$）と、それに続く $k_i$ 個の整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$（$1 \le a_{i,j} \le n$）が与えられ、$i$ 番目の数列の要素を順番に表します。

各テストケースにおいて、すべての数列にわたる $k_i$ の総和は $n$ であり、$1$ から $n$ までの各整数はすべての数列を通してちょうど 1 回ずつ現れることが保証されます。

すべてのテストケースにわたる $n$ の総和は $10^6$ を超えず、すべてのテストケースにわたる $m$ の総和も $10^6$ を超えないことが保証されます。

出力

各テストケースについて、$p$ に含まれる不動点の個数の最小値を表す単一の整数を 1 行に出力してください。

入出力例

入力 1

4
1 1
1 1
3 2
1 1
2 2 3
3 2
2 1 3
1 2
4 2
3 2 1 3
1 4

出力 1

1
0
1
0

注記

1 番目のサンプルテストケースでは、あり得る唯一の順列は $[1]$ であり、不動点を 1 個持ちます。

2 番目のサンプルテストケースでは、Little Cyan Fish は $p = [2, 3, 1]$ を得ることができ、これは不動点を持ちません。

3 番目のサンプルテストケースでは、$p = [1, 3, 2]$ が不動点を 1 個持つ最適な順列です。

4 番目のサンプルテストケースでは、彼は $p = [2, 4, 1, 3]$ を得ることができ、これは不動点を持ちません。