Galactic Breakup

Time limit1sMemory limit128 MB

Summary

Given three dimensional grid cell labels and the cell lists of the monarchies seceding in a fixed order, count the months after which the remaining cells form two or more pieces.

Level: Medium7 of 10
Topics: Union-find, Graph, Simulation
Solved: No attempts yet

Problem

After ruling a large chunk of the galaxy for millennia, a vast empire is finally breaking up into a collection of independent monarchies. The empire is very organized and takes the shape of a gigantic cube with dimensions $n$ by $m$ by $k$ parsecs. (Only a few know the exact values of $n$ , $m$ , and $k$ .) To facilitate control, it is partitioned into $n \cdot m \cdot k$ smaller dominions, each exactly $1$ cubic parsec in size.

The dominions are numbered as follows. The dominion at coordinates $(x, y, z)$ ( $0 \le x < n$ , $0 \le y < m$ , $0 \le z < k$ ) has number

$x + n \cdot y + n \cdot m \cdot z$

so the numbers run from $0$ to $n \cdot m \cdot k - 1$ , with $x$ increasing fastest, then $y$ , then $z$ . Two dominions are neighbors (share a face) exactly when precisely one of their three coordinates differs by $1$ and the other two are equal.

The empire is divided into $l$ independent monarchies. Each monarchy is a connected set of one or more dominions (connected through shared faces), and the $l$ monarchies together partition all $n \cdot m \cdot k$ dominions. Over a period of several months, exactly one monarchy per month secedes from the empire, in the given order (monarchy 1 first, then 2, and so on). On the first day of month $i$ , monarchy $i$ leaves the empire. After each secession, the remaining empire is the union of the monarchies that have not yet seceded.

Determine, over the course of the breakup, the number of months during which the remaining empire is disconnected (that is, its dominions form two or more separate connected pieces). A remaining empire that is empty or forms a single piece counts as connected.

Input

The first line contains the number of test cases $T$ .

Each test case begins with a line of four integers $n\ m\ k\ l$ ( $1 \le n, m, k \le 30$ ; $l$ is the number of monarchies). The following $l$ lines describe the monarchies in the order in which they secede. Each has the form $p\ d_1\ d_2\ \dots\ d_p$ , where $p$ ( $1 \le p \le 20$ ) is the number of dominions in the monarchy and $d_1, \dots, d_p$ are their numbers. The $l$ monarchies partition all $n \cdot m \cdot k$ dominions.

Output

For each test case, print a single line containing one integer: the number of months during which the remaining empire was disconnected.

Examples4

Example 1

Input

2
2 2 3 9
2 4 5
3 6 8 10
1 7
1 2
1 11
1 9
1 1
1 0
1 3
2 2 3 3
4 0 1 2 3
4 4 5 6 7
4 8 9 10 11

Expected output

4
0

Example 2
Input
```
1
1 1 1 1
1 0
```
Expected output
```
0
```
Example 3
Input
```
1
1 1 3 3
1 1
1 0
1 2
```
Expected output
```
1
```
Example 4
Input
```
1
1 1 3 3
1 0
1 1
1 2
```
Expected output
```
0
```