Mineshaft

A plumber has been hired to run an air pipe through a mineshaft, from the bottom of the shaft up to the surface. The shaft was dug without modern equipment, so it winds its way up through the earth. Carrying the pipe bending tools down the shaft takes a great deal of time, so the plumber wants to minimize the number of bends in the pipeline.

For the mineshaft in the first picture below, the smallest possible number of bends is two. Several optimal pipelines exist, and the second picture shows one of them. The bullets mark the bends.

Each wall of the mineshaft is a sequence of straight segments, and the two walls need not have the same number of segments. The horizontal distance between the walls varies as well, but it is always positive. Both walls start at the same level and end at the same level.

On the way from the bottom of the shaft to the surface, the level (the $y$ coordinate) increases along every segment of a wall. The shaft therefore has no horizontal plateaus or ceilings, and at no point does it go back down.

For this task the diameter of the pipeline is $0$. The pipeline may never cross a wall. To attach the pipeline firmly, every segment of the pipeline has to touch the walls in at least two different places. The bending points are weak and cannot be used to attach the pipeline. The end points of the pipeline, at the bottom and at the top of the shaft, may attach a segment, but only where they touch a wall.

That is why the third picture above, which also has two bends, is not allowed. Its lowest segment touches the walls in only one place, the foot of the right wall.

The pipeline must start anywhere at the bottom of the mineshaft and must end anywhere on the imaginary line between the top of the left wall and the top of the right wall. An end point of the pipeline attaches the pipeline only when it touches a wall. In particular, an end point at the bottom attaches nothing unless it sits exactly at the foot of a wall.

The angle $\alpha$ that the pipeline makes at a bending point may take any value with $-180^\circ < \alpha < 180^\circ$ and $\alpha \neq 0$.

Letting the pipeline intersect itself is sometimes useful. In the mineshaft below it is the only way to get from the bottom to the top with three bends.

The first line contains the number of test cases. Each test case has the following format.

• One line with one integer $N_1$ $(2 \le N_1 \le 25)$, the number of points describing the left wall of the mineshaft.
• $N_1$ lines with the points describing the left wall, from the bottom to the top. The $i$th line contains two integers $x_i$ and $y_i$ $(-1000 \le x_i \le 1000$, $0 \le y_i \le 1000)$ separated by a single space, the $x$ and $y$ coordinate of the point. The $y$ coordinates increase: $y_1 < y_2 < \cdots < y_{N_1}$.
• One line with one integer $N_2$ $(2 \le N_2 \le 25)$, the number of points describing the right wall of the mineshaft.
• $N_2$ lines with the points describing the right wall, from the bottom to the top, in the same format, with $y'_1 < y'_2 < \cdots < y'_{N_2}$.

Every test case satisfies $x_1 < x'_1$, $y_1 = y'_1$, $x_{N_1} < x'_{N_2}$ and $y_{N_1} = y'_{N_2}$. The two walls never cross and never touch.

For every test case, print one line with a single number: the minimum number of bends in a pipeline that runs from the bottom of the mineshaft to the top under the conditions above.

The test cases below correspond to the pictures in the statement.