Description

In a secret military base, a new communication technology is being tested. For the experiment, $m$ antennas were constructed inside.

The terrain around the base is perfectly flat, and the base, seen from above, is a convex polygon. The boundary of the polygon is a wall that protects the base from intruders, as well as blocks the radio waves from leaving the base to be possibly intercepted by foreign agents.

Unfortunately, some construction works are required in the facility, and two of the polygon’s walls must be torn down. This creates a security risk: if two spies are placed outside the base in such a way that two of the antennas lie on the line between them, and there is no wall blocking this line, then the spies may listen to the communication between those two antennas.

Your goal is, for some possible scenarios of removal of two walls, to determine the number of
pairs of antennas which are compromised in the way described above.

The picture above corresponds to the first case of the example input from the “Example” section. In this case, the base is a pentagon with four antennas, denoted by little crosses. All the lines between pairs of antennas are also shown.

Input Format

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 200\,000$). The test cases
follow, each one in the following format:

The first line of a test case contains an integer $n$ ($3 \leq n \leq 10$) – the number of vertices of
the polygon. The next $n$ lines contain two integers – the coordinates of the vertices, presented
clockwise. The vertices are numbered $0, 1, \ldots, n-1$ in order in which they appear.

The next line contains an integer $m$ ($2 \leq m \leq 50\,000$) – the number of antennas inside the
base – and the $m$ following lines contain the coordinates of the antennas.

The next line contains another integer $q$ ($1 \leq q \leq 10$) – the number of scenarios to consider.
The last $q$ lines describe scenarios – the $i$-th line contains two integers $a_i$, $b_i$ ($0 \leq a_i < b_i \leq n-1$).
Such a pair denotes removing the walls $a_i$ and $b_i$ and requires to compute the number of distinct
lines that go through some two antennas and do not cross neither the segment between the vertices $a_i$ and $a_i + 1$ nor the segment between $b_i$ and $(b_i + 1) \bmod n$.

All coordinates are integers whose absolute values do not exceed $10^9$. In any single testcase, all points of the input are distinct and no three of them are collinear.

Every test case, including the first, is preceded by a single empty line.

The sum of all $m$ values in all test cases does not exceed $300\,000$.

Output Format

For every testcase output, in separate lines, the answers to all given scenarios.

2

5
0 0
0 5
3 7
6 5
6 0
4
1 2
1 3
5 2
5 3
3
0 3
1 4
1 2

4
-1 -1
-1 1
2 1
2 -1
2
0 0
1 0
6
0 1
0 2
0 3
1 2
1 3
2 3

4 1 0
0 1 0 0 0 0