Turret

Problem Description

Monsters come out of the building. Please set up turrets to resist the monsters. On a two-dimensional plane, there are four walls forming a square area, with the lower left corner located at $(0,0)$ and the upper right corner located at $(10000,10000)$. There are n buildings in the area, and each building is formed by m points in counterclockwise order. For each building, the first given point is the monster spawn point. Every building is convex and any two buildings do not overlap or contact. You can set up turrets at any position outside buildings, including the edges of the buildings and the walls. Note that the coordinates of the turret do not need to be integers. A spawn point can be attacked by a turret when the link of them does not pass inside any building. Please calculate the minimum number of turrets needed to ensure that each monster spawn point can be attacked by at least one turret.

Input

The first line of the input contains a single integer $T\ (1 \le T \le 10)$, indicating the number of test cases. In each test case: The first line contains a single integer $n\ (1\le n\le 15)$, representing the number of buildings. For each building: The first line contains one integer $m\ (3 \le m \le 20)$ Each of the next m lines contains two integer number $x_i,y_i\ (0 < x_i,y_i < 10000)$, representing the $i$-th point of the building. It's guarenteed that the for each test case the sum of $m$ do not exceed 200.

Output

Output an integer representing the minimum number of turrets needed.

Sample Input

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

Sample Output

1

Hint

You can set up a turret at $(0,10)$

Source

2023“钉耙编程”中国大学生算法设计超级联赛（2）