题目背景

Source: AMPPZ 2019.

题目描述

某秘密军事基地正在测试新型通信技术，基地内部建造了 $m$ 个天线。

从俯视图看，基地是一个凸多边形区域，其边界围墙既用于防范入侵者，也能阻挡无线电波外泄以免被外国间谍截获。

由于施工需要，基地必须拆除两段围墙。这将导致安全隐患：若两名间谍被安置在基地外，且某两个天线的连线经过这两名间谍所在位置，同时该连线未被剩余围墙阻挡，则间谍可能窃听这两个天线间的通信。

你的任务是为每种拆除两段围墙的场景，计算因此暴露的天线对数量（即连接该对天线的直线不再被任何围墙阻挡）。

（上方图示对应样例输入的第一组数据，展示了一个五边形基地和四个天线的分布情况，图中标出了所有天线间的连线。）

输入格式

本题单个测试点内有多组测试数据。
输入的第一行包含测试数据数量 $z$（$1 \leq z \leq 200\,000$）。每组测试数据的格式如下：

每组测试数据以空行开始。
第一行包含一个整数 $n$（$3 \leq n \leq 10$）——多边形的顶点数。接下来 $n$ 行每行包含两个整数，按顺时针顺序给出各顶点的坐标。顶点依次编号为 $0, 1, \ldots, n-1$。

下一行包含一个整数 $m$（$2 \leq m \leq 50\,000$）——基地内的天线数量，随后 $m$ 行给出各天线的坐标。

接着一行包含整数 $q$（$1 \leq q \leq 10$）——需考虑的场景数量。最后 $q$ 行描述场景——第 $i$ 行包含两个整数 $a_i$, $b_i$（$0 \leq a_i < b_i \leq n-1$）。该组数字表示拆除顶点 $a_i$ 与 $a_i + 1$ 之间、以及 $b_i$ 与 $(b_i + 1) \bmod n$ 之间的两段围墙，要求计算满足以下条件的天线对数量：连接该对天线的直线既不穿过被拆除的第一段围墙，也不穿过被拆除的第二段围墙。

所有坐标均为绝对值不超过 $10^9$ 的整数。单个测试数据中所有输入点互不相同且任意三点不共线。
所有测试数据的 $m$ 值总和不超过 $300\,000$。

输出格式

对于每个测试数据的每个场景，输出一行对应的答案。

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