题目描述

怪物从建筑物中出现。请设置炮塔来抵抗怪物。

在一个二维平面上，有四堵墙围成一个正方形区域，左下角位于 $(0,0)$，右上角位于 $(10000,10000)$。

该区域内有 $n$ 座建筑物，每个建筑物由按逆时针顺序给出的 $m$ 个点构成。对于每个建筑物，给出的第一个点是怪物生成点。每个建筑物都是凸的，并且任意两个建筑物不重叠也不接触。

你可以在建筑物外部的任何位置设置炮塔，包括建筑物的边缘和墙壁上。注意，炮塔的坐标不必须是整数。当一个生成点与炮塔之间的连线不穿过任何建筑物的内部时，该生成点就可以被这个炮塔攻击到。

请计算确保每个怪物生成点都至少能被一个炮塔攻击到所需的最少炮塔数量。

输入格式

输入的第一行包含一个整数 $T$（$1 \leq T \leq 10$），表示测试用例的数量。

在每个测试用例中：

第一行包含一个整数 $n$（$1 \leq n \leq 15$），表示建筑物的数量。

对于每个建筑物：

第一行包含一个整数 $m$（$3 \leq m \leq 20$）。

接下来的 $m$ 行，每行包含两个整数 $x_i, y_i$（$0 < x_i, y_i < 10000$），表示建筑物的第 $i$ 个点。

保证每个测试用例中所有建筑物的 $m$ 之和不超过 $200$。

输出格式

输出一个整数，表示所需的最少炮塔数量。

1
4
4
1 1
2 1
2 2
1 2
4
3 3
4 3
4 4
3 4
4
3 1
4 1
4 2
3 2
4
1 3
2 3
2 4
1 4

1

解释 #1

你可以将炮塔设置在 $(0, 10)$ 处。