Hexagonal Sticks

Consider an infinite hexagonal grid made of identical regular hexagonal cells arranged as shown below. The figure also shows the coordinate system used to identify each cell. Every cell is either empty or blocked.

Figure: A portion of the grid

A number of sticks are placed on the grid. Each stick has a length of one hexagonal unit: its two endpoints lie on the centers of two neighbouring cells. Your task is to move the sticks so that they form a single closed regular hexagon. The pictures below show some closed hexagonal figures built from sticks.

Hexagon with 6 sticks	Hexagon with 6 sticks	Hexagon with 12 sticks

You are given the initial coordinates of the sticks together with the coordinates of the blocked cells. In one move you may do exactly one of the following:

• pick a stick and throw it away;
• pick a stick and rotate it 60° clockwise or anti-clockwise about one of its endpoints;
• pick a stick and push it one unit along its own length.

A stick may never occupy a blocked cell. Two sticks, however, are allowed to occupy the same cells at the same time.

Consider the situation above: a blocked cell at (1, 1) and a stick from (0, 0) to (1, 0). The four possible moves are shown below.

Rotate 60° clockwise about (0, 0)	Rotate 60° anti-clockwise about (1, 0)	Push along the length	Push along the length

After all moves are made, the remaining sticks must form exactly one closed regular hexagon with no leftover sticks. In other words the grid must contain exactly $6x$ sticks for some positive integer $x$, and they must form one closed hexagonal outline. Find the minimum number of moves needed.

The first line contains an integer $T$ ($T < 50$), the number of test cases. Each test case begins with a non-negative integer $S$ ($S < 9$), the number of sticks. Each of the next $S$ lines contains four integers x1 y1 x2 y2, describing a stick from $(x_1, y_1)$ to $(x_2, y_2)$; every stick has length exactly one hexagonal unit. The next line contains a non-negative integer $B$ ($B < 20$), the number of blocked cells, followed by $B$ lines each containing two integers x y for one blocked cell. No blocked cell coincides with a stick. All given coordinates lie in the range $[-4, 4]$.

Note: the grid is infinite, so in an optimal solution the final hexagon may use cells outside $[-4, 4]$.

For each test case print one line in the form Case i: m, where $i$ is the test-case number (starting from 1) and $m$ is the minimum number of moves required. If it is impossible to form a closed hexagon, print Case i: impossible instead.