육각형 막대

무한히 뻗은 육각형 격자를 생각하자. 격자는 아래 그림처럼 배열된, 크기가 같은 정육각형 칸들로 이루어진다. 그림에는 각 칸을 가리키는 좌표계도 함께 나타나 있다. 각 칸은 비어 있거나 막혀 있다.

그림: 격자의 일부

이 격자 위에 여러 개의 막대가 놓여 있다. 각 막대의 길이는 정확히 1 육각 단위이며, 두 끝점은 서로 이웃한 두 칸의 중심에 놓인다. 목표는 막대들을 움직여 하나의 닫힌 정육각형을 만드는 것이다. 아래 그림들은 막대로 만든 닫힌 육각형의 예이다.

막대 6개로 만든 육각형	막대 6개로 만든 육각형	막대 12개로 만든 육각형

막대들의 처음 좌표와 막힌 칸들의 좌표가 주어진다. 한 번의 이동으로 다음 중 정확히 하나를 할 수 있다.

• 막대 하나를 골라 버린다.
• 막대 하나를 골라 한 끝점을 중심으로 시계 방향 또는 반시계 방향으로 60° 회전한다.
• 막대 하나를 골라 자신의 길이 방향으로 한 칸 민다.

막대는 막힌 칸을 절대 차지할 수 없다. 다만 두 막대가 같은 칸을 동시에 차지하는 것은 허용된다.

위 상황을 보자. (1, 1)에 막힌 칸이 있고 (0, 0)에서 (1, 0)으로 가는 막대가 있다. 가능한 네 가지 이동은 아래와 같다.

(0, 0)을 중심으로 시계 방향 60° 회전	(1, 0)을 중심으로 반시계 방향 60° 회전	길이 방향으로 밀기	길이 방향으로 밀기

모든 이동을 끝낸 뒤에는, 남은 막대들이 정확히 하나의 닫힌 정육각형을 이루어야 하며 남는 막대가 있어서는 안 된다. 즉 격자에는 어떤 양의 정수 $x$에 대해 정확히 $6x$개의 막대가 있어야 하고, 그것들이 하나의 닫힌 육각형 윤곽을 이루어야 한다. 필요한 최소 이동 횟수를 구하라.

첫 줄에 테스트 케이스의 수를 나타내는 정수 $T$ ($T < 50$)가 주어진다. 각 테스트 케이스는 막대의 개수를 나타내는 음이 아닌 정수 $S$ ($S < 9$)로 시작한다. 이어지는 $S$개의 줄에는 각각 네 정수 x1 y1 x2 y2가 주어지며, 이는 $(x_1, y_1)$에서 $(x_2, y_2)$로 가는 막대를 뜻한다. 모든 막대의 길이는 정확히 1 육각 단위이다. 그다음 줄에는 막힌 칸의 개수를 나타내는 음이 아닌 정수 $B$ ($B < 20$)가 주어지고, 이어지는 $B$개의 줄에 각각 두 정수 x y로 막힌 칸 하나의 좌표가 주어진다. 막힌 칸은 어떤 막대와도 겹치지 않는다. 주어지는 모든 좌표는 $[-4, 4]$ 범위 안에 있다.

참고: 격자는 무한하므로, 최적해에서 완성되는 육각형은 $[-4, 4]$ 바깥의 칸을 사용할 수도 있다.

각 테스트 케이스마다 Case i: m 형식으로 한 줄을 출력한다. 여기서 $i$는 테스트 케이스 번호(1부터 시작)이고 $m$은 필요한 최소 이동 횟수이다. 닫힌 육각형을 만들 수 없으면 대신 Case i: impossible을 출력한다.