题目描述

农夫 John 的牧场形状十分特殊。

牧场中有 $N$ 根木桩，它们构成一个凸多边形。对于任意一对木桩，都有一根笔直的绳子连接这两根木桩。由于这些绳子架得很高，奶牛很难从绳子上方越过。

奶牛 Alice 和 Bessie 是彼此最好的朋友。但是，农夫 John 将她们分开了，因此她们目前相距很远。

上图给出了 $N=4$ 时的一种情况。此时一共有 $6$ 根绳子。

Alice 想前往 Bessie 所在的位置与她见面。由于越过绳子并不容易，因此 Alice 希望选择一条路径，使途中越过的绳子数量尽可能少。

Alice 前往 Bessie 的最优路径示意图

在上图所示的情况下，最优路径需要越过 $2$ 根绳子。

由于农夫 John 经常改变两头奶牛的位置，你需要回答 $Q$ 次询问。对于每次询问，求 Alice 从给定位置移动到 Bessie 的给定位置时，最少需要越过多少根绳子。

请帮助 Alice 和 Bessie 解决这个问题。

需要注意：

• 如果路径经过多根绳子的交点，则穿过每一根绳子都要分别计数。
  例如，如果路径恰好经过三根绳子的公共交点，则视为越过了 $3$ 根绳子，而不是只越过一次。
• 如果路径多次越过同一根绳子，则每次都要分别计数。

输入格式

第一行包含一个整数 $N$，表示木桩的数量。

接下来的 $N$ 行，每行包含两个整数 $x,y$，表示一根木桩的坐标。

这些木桩按照其在凸多边形边界上的逆时针顺序给出。

接下来一行包含一个整数 $Q$，表示询问数量。

接下来的 $Q$ 行，每行包含四个整数：

其中：

• $(x_1,y_1)$ 表示 Alice 的位置；
• $(x_2,y_2)$ 表示 Bessie 的位置。

输出格式

对于每次询问，输出一行一个整数，表示 Alice 到达 Bessie 所在位置时，最少需要越过的绳子数量。

答案应按照询问在输入中的顺序输出。

数据范围

所有输入坐标的绝对值均不超过 $10^8$。

此外，保证：

• $N$ 根木桩构成一个严格凸多边形，即每个内角都小于 $180^\circ$；
• 每头奶牛的位置都不在任何一根绳子上；
• 对于每次询问，所有木桩以及 Alice、Bessie 的位置两两不同。

样例输入

4
-5 -5
5 -5
5 5
-5 5
3
0 2 0 -2
2 0 -2 0
6 0 0 -6

样例输出

2
2
0