你刚刚穿越到了另一个世界，并得到了一张这个世界的地图。这个世界有若干个国家。每个国家都有一个连通的领土，在地图上被绘制为一个简单的多边形，由其在二维平面上的边界线段组成。

你对这个世界感到陌生，因此你想给地图上的国家涂色以区分它们。如果你给相邻的国家涂上相同的颜色，那么区分这些国家将会非常困难。因此，你希望给相邻的国家涂上不同的颜色。在这里，我们定义两个国家是相邻的，当且仅当它们的边界至少有一条长度严格大于 0 的公共线段。注意，如果两个国家的边界仅在点上接触，则它们不被视为相邻。

由于你没有这个世界的货币，你很难准备太多的颜色。请问给地图涂色，使得相邻国家颜色不同的最少颜色数是多少？

输入格式

输入包含多组数据集。数据集的数量不超过 35 个。

每个数据集的第一行包含一个整数 $n$ ($1 \le n \le 35$)，表示这个世界中国家的数量。

每个数据集的其余部分描述了代表国家的 $n$ 个多边形的信息。第 $i$ 个多边形信息的第一行包含一个整数 $m_i$ ($3 \le m_i \le 50$)，表示顶点的数量。接下来的 $m_i$ 行按逆时针顺序描述了顶点的坐标。

其中第 $j$ 行包含两个整数 $x_{i,j}$ 和 $y_{i,j}$ ($|x_{i,j}|, |y_{i,j}| \le 10^3$)，表示第 $i$ 个多边形的第 $j$ 个顶点的坐标。

你可以假设以下条件成立：

• 每个多边形的面积大于 0。
• 同一个多边形的任意两个顶点坐标互不相同。
• 同一个多边形的任意两条线段除了在每个顶点处恰好相交外，没有其他公共点。
• 任意两个多边形没有公共面积。

输入的结尾由一行包含单个零的行表示。

输出格式

对于每个数据集，输出一行，表示给地图涂色使得相邻国家颜色不同的最少颜色数。

样例

样例输入 1

1
3
0 0
1 0
0 1
4
4
0 0
10 0
10 10
0 10
4
10 0
20 0
20 10
10 10
4
0 10
10 10
10 20
0 20
4
10 10
20 10
20 20
10 20
3
4
-10 -10
2 2
10 10
-11 7
3
-1 -1
1 -1
0 0
3
0 0
3 -3
20 20
0

样例输出 1

1
2
3

样例输入 2

7
4
46 12
52 12
53 15
45 15
32
67 1
70 0
73 1
77 3
79 5
80 8
77 8
76 5
74 4
71 3
70 3
67 4
65 6
63 8
62 14
64 19
66 21
70 22
75 21
78 16
80 16
80 17
79 20
78 22
74 24
67 24
63 22
61 19
60 15
60 10
62 5
64 3
5
74 14
80 14
80 16
78 16
74 16
19
34 0
37 0
37 19
36 22
35 23
32 24
30 24
27 24
25 23
23 20
23 18
23 15
26 15
26 18
27 20
29 21
32 21
34 20
34 18
4
47 0
50 0
42 24
39 24
4
79 20
80 17
80 22
78 22
4
50 0
58 24
56 24
49 3
0

样例输出 2

3

样例输入 3

4
10
34 21
34 14
35 14
35 19
40 19
40 20
35 20
35 22
30 22
30 21
16
20 24
21 24
21 33
42 33
42 20
40 20
40 19
45 19
45 5
40 5
40 4
46 4
46 20
43 20
43 34
20 34
10
26 21
26 14
27 14
27 21
30 21
30 22
21 22
21 24
20 24
20 21
12
34 8
34 4
40 4
40 5
35 5
35 14
34 14
34 9
27 9
27 14
26 14
26 8
0

样例输出 3

4