你有一个凸多边形。多边形的顶点按顺序编号为 $1$ 到 $n$。你还拥有该多边形的一个三角剖分，由 $n-3$ 条对角线列表给出。

你还需要处理 $q$ 个询问。每个询问包含两个顶点索引。对于每个询问，请找出这两个顶点之间的最短距离，前提是你只能沿着多边形的边和给定的对角线移动，且距离定义为所经过的边和对角线的总数。

输入格式

输入文件的第一行包含一个整数 $n$ —— 多边形的顶点数 ($4 \le n \le 50\,000$)。

接下来的 $n-3$ 行，每行包含两个整数 $a_i, b_i$ —— 第 $i$ 条对角线的两个端点 ($1 \le a_i, b_i \le n, a_i \neq b_i$)。

下一行包含一个整数 $q$ —— 询问次数 ($1 \le q \le 100\,000$)。

接下来的 $q$ 行，每行包含两个整数 $x_i, y_i$ —— 第 $i$ 个询问中的两个顶点 ($1 \le x_i, y_i \le n$)。

保证没有对角线与多边形的边重合，且没有两条对角线重合或相交。

输出格式

对于每个询问，输出一行，包含最短距离。

样例

输入格式 1

6
1 5
2 4
5 2
5
1 3
2 5
3 4
6 3
6 6

输出格式 1

2
1
1
3
0

说明

这是样例输入对应的多边形。