Museum Tour

A large museum has many rooms and many corridors. Planning a tour through it takes real work, so the museum put a simple rule on its signs and asks visitors to follow it.

If room $v$ has $d$ doors leading through corridors to other rooms, those doors and the matching corridors carry numbers $1, 2, \dots, d$ that are used only inside that room. The rule has two parts.

• In the room where the tour starts, leave through door $1$.
• If you entered a room through door $i$, leave through the door with the next number: door $i + 1$ when $i < d$, and door $1$ when $i = d$.

The picture below shows a tour that starts in room $1$ and passes rooms $1, 2, 3, 4, 5, 6$ in this order, walking through every corridor at least once.

Exhibits hang in the corridors as well as in the rooms. What matters is whether a visitor who follows the rule, does not get bored, and walks long enough finally passes through every corridor at least once. Call a room a good starting room when a tour that begins there does exactly that.

The door numbers are already fixed and are given in the input. Count the good starting rooms.

At most 3 corridors leave each room, and the whole museum is connected: you can walk between any two rooms, possibly passing through other rooms on the way. All corridors leaving one room lead to different rooms.

The input contains several test cases. The first line contains the number of test cases $t$ ($t \le 100$).

Each test case begins with a line containing the number of rooms $n$ ($3 \le n \le 10^5$). The next $n$ lines describe the doors, one line per room, in order of the door numbers. Line $i$ starts with the number of doors $d$ ($1 \le d \le 3$), followed by $d$ integers $r_1, r_2, \dots, r_d$. Here $r_j$ is the room that door $j$ of room $i$ leads to ($1 \le r_j \le n$, $r_j \ne i$, and $r_j \ne r_k$ when $j \ne k$).

All corridors are bidirectional, so if there is a door from room $x$ to room $y$, there is a door from room $y$ to room $x$ as well. The total size of the input does not exceed 50MB.

For each test case, print the number of good starting rooms on one line.