박물관 순회

넓고 화려한 박물관이 있다. 방도 많고 복도도 많아서 관람 순서를 짜는 일 자체가 큰 일이다. 그래서 박물관은 관람객이 따라 걷기만 하면 되는 간단한 규칙을 안내판에 붙여 두었다.

방 $v$에 다른 방으로 이어지는 문이 $d$개 있으면, 그 문과 문에 이어진 복도에는 그 방 안에서만 쓰는 번호 $1, 2, \dots, d$가 붙어 있다. 관람 규칙은 두 가지다.

• 관람을 시작하는 방에서는 $1$번 문으로 나간다.
• $i$번 문으로 어떤 방에 들어왔다면 다음 번호 문으로 나간다. 즉 $i < d$이면 $i + 1$번 문, $i = d$이면 $1$번 문으로 나간다.

아래 그림은 관람객이 $1$번 방에서 출발해 $1, 2, 3, 4, 5, 6$번 방을 차례로 지나면서 모든 복도를 한 번 이상 걷는 예다.

복도에도 전시물이 걸려 있다. 그래서 규칙을 지키며 지루해하지 않고 충분히 오래 걷는 관람객이 결국 모든 복도를 한 번 이상 지나는지가 중요하다. 이 조건을 만족하는 출발 방을 좋은 출발점이라고 하자.

문 번호는 이미 정해져 있고 입력으로 주어진다. 좋은 출발점인 방이 몇 개인지 세어라.

한 방에서 나가는 복도는 많아야 3개이고, 박물관 전체는 연결되어 있다. 즉 어떤 두 방 사이든 중간에 다른 방을 거치더라도 걸어서 오갈 수 있다. 한 방에서 나가는 복도는 모두 서로 다른 방으로 이어진다.

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에 테스트 케이스의 수 $t$ ($t \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 방의 수 $n$ ($3 \le n \le 10^5$)이 주어진다. 이어지는 $n$개 줄 중 $i$번째 줄은 $i$번 방의 문을 번호 순서대로 설명한다. 먼저 문의 개수 $d$ ($1 \le d \le 3$)가 주어지고, 정수 $r_1, r_2, \dots, r_d$가 이어진다. $r_j$는 $i$번 방의 $j$번 문이 이어지는 방의 번호다 ($1 \le r_j \le n$, $r_j \ne i$, $j \ne k$이면 $r_j \ne r_k$).

모든 복도는 양방향이다. $x$번 방에서 $y$번 방으로 가는 문이 있으면 $y$번 방에서 $x$번 방으로 가는 문도 있다. 입력 전체 크기는 50MB를 넘지 않는다.

각 테스트 케이스마다 좋은 출발점인 방의 개수를 한 줄에 출력한다.