在一个秘密军事基地中，一项新的通信技术正在进行测试。实验中，基地内部建造了 $m$ 个天线。

基地周围的地形完全平坦，从上方俯瞰，基地是一个凸多边形。多边形的边界是一堵墙，既能保护基地免受入侵者的侵害，也能阻挡无线电波离开基地，防止被外国特工截获。

不幸的是，设施内需要进行一些施工，必须拆除多边形的其中两堵墙。这带来了安全风险：如果两名间谍被安置在基地外，使得两个天线位于他们之间的连线上，且没有墙壁阻挡这条线，那么间谍就可能窃听这两个天线之间的通信。

你的目标是针对拆除两堵墙的某些可能方案，确定在这种情况下被泄露的天线对的数量。

上图对应“样例”部分中第一个测试用例的情况。在这种情况下，基地是一个五边形，有四个天线，用小十字表示。图中还显示了天线对之间的所有连线。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 200\,000$)。接下来是各个测试用例，格式如下：

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 10$) —— 多边形的顶点数。接下来的 $n$ 行包含两个整数 —— 顶点的坐标，按顺时针顺序给出。顶点按其出现的顺序编号为 $0, 1, \dots, n-1$。

下一行包含一个整数 $m$ ($2 \le m \le 50\,000$) —— 基地内天线的数量，接下来的 $m$ 行包含天线的坐标。

下一行包含另一个整数 $q$ ($1 \le q \le 10$) —— 需要考虑的方案数。最后 $q$ 行描述方案 —— 第 $i$ 行包含两个整数 $a_i, b_i$ ($0 \le a_i < b_i \le n-1$)。这样的一对数表示拆除墙壁 $a_i$ 和 $b_i$，并要求计算穿过某两个天线且不与顶点 $a_i$ 和 $a_i+1$ 之间的线段相交，也不与顶点 $b_i$ 和 $(b_i+1) \pmod n$ 之间的线段相交的独特直线的数量。

所有坐标均为整数，其绝对值不超过 $10^9$。在任何单个测试用例中，输入的所有点都是不同的，且没有三点共线。

每个测试用例（包括第一个）之前都有一个空行。

所有测试用例中 $m$ 的总和不超过 $300\,000$。

输出格式

对于每个测试用例，在单独的行中输出所有给定方案的答案。

样例

输入 1

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

输出 1

4 1 0
0 1 0 0 0 0

上图对应“样例”部分中第一个测试用例的情况。在这种情况下，基地是一个五边形，有四个天线，用小十字表示。图中还显示了天线对之间的所有连线。