描述

在统治银河系的大部分区域数千年后，宇宙过时的寡头帝国（COBOL）终于分裂成一系列独立的君主制国家。COBOL 是一个非常有组织的帝国，其形状是一个巨大的立方体，尺寸为 $n * m * k$ 秒差距。(COBOL 也非常保密，因此只有少数人知道 $n$、$m$ 和 $k$ 的具体值。）为了便于管理，帝国被划分为 $nmk$ 个较小的领土，每个领土的大小为 $1$ 立方秒差距。这些领土的编号如下：

每个独立的君主制国家是一个由一个或多个领土组成的连通区域（如果两个领土共享一个面，它们是连通的）。在接下来的几个月里，每个月将有一个君主制国家从帝国分裂出去。每次分裂从每个月的第一天开始。COBOL 关心的问题是，在分裂过程中，剩余帝国的某些部分可能变得不再连通，这可能会妨碍剩余帝国的管理。你的任务是确定在分裂过程中，帝国变得不连通的月份数量。

输入

输入将包括多个问题实例。第一行将包含一个正整数，表示接下来要处理的问题实例的数量。每个问题实例的第一行将包含四个整数：$n$ $m$ $k$ $l$，其中 $n$、$m$ 和 $k$ 如前所述，$1 <= n, m, k <= 30$，$l$ 是帝国被分裂成的独立君主制国家的数量。接下来的 $l$ 行定义了这些君主制国家。每行的形式为 $p$ $d1$ $d2$ $d3$ $...$ $dp$，其中 $p$ 是组成该君主制国家的领土数量（$1 <= p <= 20$），$d1$$,$ $d2$$,$ $...$ $,$ $dp$ 是这些领土的编号。君主制国家按照它们从帝国分裂的顺序列出。

输出

对于每个问题实例，输出一行，包含一个整数，表示帝国不连通的月份数量。

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

4
0

来源

East Central North America 2002