Little Cyan Fish ha $m$ sequenze costituite da $n$ interi in totale. Ogni intero da $1$ a $n$ compare esattamente una volta considerando tutte le sequenze.

Vuole unire queste sequenze in una permutazione $p$ di lunghezza $n$. Inizialmente, $p$ è vuota. A ogni passo, sceglie una sequenza non vuota, rimuove il suo primo intero e aggiunge questo intero alla fine di $p$. Ripete questa operazione finché tutte le sequenze non sono vuote.

Un intero è chiamato punto fisso di $p$ se il suo valore è uguale alla sua posizione in $p$. Le posizioni sono numerate da $1$ a $n$.

Trova il minimo numero possibile di punti fissi in $p$.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^6$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene due interi $n$ e $m$ ($1 \le m \le n \le 10^6$), che indicano rispettivamente il numero totale di interi e il numero di sequenze.

Le successive $m$ righe descrivono le sequenze. La $i$-esima di queste righe contiene un intero $k_i$ ($1 \le k_i \le n$), seguito da $k_i$ interi $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$ ($1 \le a_{i,j} \le n$), che descrivono la $i$-esima sequenza in ordine.

È garantito che la somma dei $k_i$ su tutte le sequenze in ciascun caso di test sia $n$, e che ogni intero da $1$ a $n$ compaia esattamente una volta considerando tutte le sequenze.

È garantito che la somma di $n$ su tutti i casi di test non superi $10^6$, e che la somma di $m$ su tutti i casi di test non superi $10^6$.

Output

Per ogni caso di test, stampa una singola riga contenente un singolo intero, che indica il minimo numero possibile di punti fissi in $p$.

Esempi

Input 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

Output 1

1
0
1
0

Nota

Nel primo caso di test di esempio, l'unica permutazione possibile è $[1]$, che ha un punto fisso.

Nel secondo caso di test di esempio, Little Cyan Fish può ottenere $p = [2, 3, 1]$, che non ha punti fissi.

Nel terzo caso di test di esempio, $p = [1, 3, 2]$ è una permutazione ottimale con un punto fisso.

Nel quarto caso di test di esempio, può ottenere $p = [2, 4, 1, 3]$, che non ha punti fissi.