Little Cyan Fish에게는 총 $n$개의 정수로 이루어진 $m$개의 수열이 있습니다. $1$부터 $n$까지의 각 정수는 모든 수열을 통틀어 정확히 한 번씩 등장합니다.

그는 이 수열들을 병합하여 길이가 $n$인 순열 $p$를 만들고자 합니다. 처음에 $p$는 비어 있습니다. 매 단계마다 그는 비어 있지 않은 수열을 하나 선택하고, 그 수열의 첫 번째 정수를 제거한 뒤, 이 정수를 $p$의 끝에 추가합니다. 모든 수열이 빌 때까지 이 과정을 반복합니다.

순열 $p$에 있는 어떤 정수의 값이 $p$에서의 위치와 같다면, 그 정수를 $p$의 고정점이라고 부릅니다. 위치는 $1$부터 $n$까지 번호가 매겨집니다.

$p$에 있을 수 있는 고정점의 최소 개수를 구하세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^6$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수의 총 개수와 수열의 개수를 각각 나타내는 두 정수 $n$과 $m$ ($1 \le m \le n \le 10^6$)이 주어집니다.

다음 $m$개의 줄에는 수열에 대한 정보가 주어집니다. 이 중 $i$번째 줄에는 정수 $k_i$ ($1 \le k_i \le n$)와, 이어서 $i$번째 수열을 순서대로 설명하는 $k_i$개의 정수 $a_{i,1}, a_{i,2}, \ldots, a_{i,k_i}$ ($1 \le a_{i,j} \le n$)가 주어집니다.

각 테스트 케이스에서 모든 수열에 대한 $k_i$의 합은 $n$이며, $1$부터 $n$까지의 각 정수는 모든 수열을 통틀어 정확히 한 번씩 등장함이 보장됩니다.

모든 테스트 케이스에 대한 $n$의 합은 $10^6$을 초과하지 않으며, 모든 테스트 케이스에 대한 $m$의 합도 $10^6$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 $p$에 있을 수 있는 고정점의 최소 개수를 나타내는 정수 하나를 한 줄에 출력합니다.

예제

입력 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]$이며, 고정점이 하나 있습니다.

두 번째 예제 테스트 케이스에서 Little Cyan Fish는 $p = [2, 3, 1]$을 얻을 수 있으며, 여기에는 고정점이 없습니다.

세 번째 예제 테스트 케이스에서 $p = [1, 3, 2]$는 고정점이 하나 있는 최적의 순열입니다.

네 번째 예제 테스트 케이스에서 그는 $p = [2, 4, 1, 3]$을 얻을 수 있으며, 여기에는 고정점이 없습니다.