Farmland

You are given the farmland map of a country. The whole farmland is divided into a set of disjoint farming regions, and each farmer owns exactly one region. There is a boundary fence between two neighboring regions. The map can be represented as a plane graph $G(V, E)$.

There are two kinds of edges: a boundary edge, which lies between two neighboring regions, and a non-boundary edge, which sticks into the interior of a region.

A proper farming region is a closed region bounded by a single simple cycle that contains no vertex or edge in its interior. For example, if a quadrilateral has another vertex inside it, that quadrilateral is not a proper region. A region whose bounding cycle is not simple (it repeats a vertex or an edge) is not proper either. A degenerate region with no interior area (for example, one made of only two vertices) is also not proper.

Assume the following about $G(V, E)$:

• The graph is simple and connected: there are no self-loops and no parallel edges.
• The outer (unbounded) face of $G(V, E)$ is never counted.
• There is at least one proper farming region.
• All vertex positions are distinct.
• No two edges cross, so $G(V, E)$ is a plane graph.

The size of a proper farming region is the number of boundary edges around it. For example, a quadrilateral region bounded by four edges has size $4$.

Given an integer $k$, count how many proper farming regions have size exactly $k$. If there is no such region, print $0$.

The first line contains the number of test cases $M$ ($1 \le M < 10$).

Then $M$ test cases follow. The first line of each test case contains the number of vertices $N$ ($3 \le N < 200$).

Each of the next $N$ lines describes one vertex in the form:

i xi yi di a1 a2 ... adi

Here $i$ is the vertex number, $(x_i, y_i)$ is the coordinate of vertex $i$, $d_i$ is the degree of vertex $i$, and $a_1, \dots, a_{d_i}$ are the vertices adjacent to $i$.

The last line of each test case contains $k$, the size of the proper regions you must count.

All vertices lie on grid points of a $1000 \times 1000$ lattice.

For each test case, print on its own line the number of proper farming regions whose size is exactly $k$. In other words, print $M$ non-negative integers.