갱도

배관공이 갱도 바닥에서 지표면까지 통풍관을 놓는 일을 맡았다. 이 갱도는 현대적인 장비 없이 파낸 탓에 위로 올라가면서 이리저리 굽어 있다. 관을 구부리는 공구를 지하까지 옮기는 데 시간이 아주 많이 들기 때문에, 배관공은 관을 구부리는 횟수를 최소로 줄이려고 한다.

예를 들어 아래 첫 번째 그림의 갱도에서는 바닥에서 지표면까지 놓는 관을 두 번만 구부리면 되고, 그보다 적게는 안 된다. 최적인 방법은 여러 가지이며 그중 하나가 두 번째 그림이다. 점으로 찍은 곳이 관이 굽은 지점이다.

갱도의 두 벽은 각각 선분을 이어 붙인 모양이다. 두 벽의 선분 개수는 서로 다를 수 있다. 두 벽 사이의 수평 거리도 일정하지 않지만 항상 0보다 크다. 두 벽은 같은 높이에서 시작해 같은 높이에서 끝난다.

갱도 바닥에서 지표면으로 올라가는 동안 벽의 모든 선분에서 높이, 즉 $y$좌표가 증가한다. 따라서 갱도에는 수평인 바닥이나 천장이 없고, 어느 지점에서도 다시 아래로 내려가지 않는다.

이 문제에서 관의 지름은 $0$으로 본다. 관은 어느 지점에서도 벽을 넘어가면 안 된다. 관을 벽에 단단히 붙이려면 관의 각 선분이 서로 다른 두 곳 이상에서 벽에 닿아야 한다. 그런데 관이 굽은 지점은 약해서 관을 벽에 붙이는 데 쓸 수 없다. 반면 갱도 바닥과 꼭대기에 있는 관의 양 끝점은 벽에 닿기만 하면 선분을 붙이는 데 쓸 수 있다.

그래서 위 세 번째 그림은 굽은 곳이 두 개뿐인데도 허용되지 않는다. 맨 아래 선분이 벽에 닿는 곳이 오른쪽 벽의 밑동 한 곳뿐이기 때문이다.

관은 갱도 바닥 어디에서든 시작해서, 왼쪽 벽 꼭대기와 오른쪽 벽 꼭대기를 잇는 가상의 선 위 어디에서든 끝나야 한다. 다만 관의 끝점은 벽에 닿을 때만 관을 붙이는 데 쓸 수 있다. 특히 바닥 쪽 끝점은 벽의 밑동이 아닌 위치에서는 아무것도 붙이지 못한다.

관이 굽은 지점에서 이루는 각 $\alpha$는 $-180^\circ < \alpha < 180^\circ$이고 $\alpha \neq 0$이기만 하면 어떤 값이든 된다.

관이 자기 자신과 교차하도록 놓는 편이 이로울 때도 있다. 아래 갱도에서는 그렇게 해야만 세 번만 구부려 바닥에서 꼭대기까지 갈 수 있다.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫째 줄에 왼쪽 벽을 이루는 점의 개수 $N_1$ $(2 \le N_1 \le 25)$이 주어진다.
• 다음 $N_1$개 줄에 왼쪽 벽의 점이 아래에서 위 순서로 주어진다. $i$번째 줄에는 점의 $x$좌표와 $y$좌표인 두 정수 $x_i$와 $y_i$ $(-1000 \le x_i \le 1000$, $0 \le y_i \le 1000)$가 공백 하나를 사이에 두고 주어진다. $y$좌표는 $y_1 < y_2 < \cdots < y_{N_1}$을 만족한다.
• 다음 줄에 오른쪽 벽을 이루는 점의 개수 $N_2$ $(2 \le N_2 \le 25)$가 주어진다.
• 다음 $N_2$개 줄에 오른쪽 벽의 점이 같은 형식으로 아래에서 위 순서로 주어지고, $y$좌표는 $y'_1 < y'_2 < \cdots < y'_{N_2}$를 만족한다.

모든 테스트 케이스는 $x_1 < x'_1$, $y_1 = y'_1$, $x_{N_1} < x'_{N_2}$, $y_{N_1} = y'_{N_2}$를 만족한다. 두 벽은 서로 교차하지 않고 닿지도 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 문제의 조건을 지키면서 갱도 바닥에서 꼭대기까지 관을 놓을 때 관이 굽는 곳의 최소 개수이다.

아래 테스트 케이스는 문제에 나온 그림 속 두 갱도이다.