分形树 $F_i$ 的定义如下：首先给定一个包含至少 2 个顶点的有根树 $F_0$。然后递归地定义 $F_i$：考虑 $F_{i-1}$ 中的所有叶子节点集合 $S$。对于 $S$ 中的每个顶点 $v$，我们将其替换为 $F_0$ 的一个副本，使得 $v$ 与 $F_0$ 的根节点重合。

现在，考虑给定 $k$ 时的树 $F_k$。在这棵树中，我们进行深度优先搜索，递归地访问树的所有顶点。在某个顶点处，我们首先递归访问该顶点的最左侧子树，然后是第二个最左侧子树，以此类推，直到访问完该顶点子树中的所有顶点。按照访问顺序为顶点分配从 1 开始的整数标签。示例请参见图 F.1。

图 F.1：样例输入 1 的说明。

给定一组由顶点对组成的查询，你的任务是找出这两个顶点之间的距离。距离定义为两个顶点之间（唯一）简单路径上的边数。

输入格式

首先给出树 $F_0$。输入的第一行包含 $F_0$ 中的顶点数 $2 \le n \le 100\,000$。顶点编号为 $0$ 到 $n-1$，其中 $0$ 为根节点。接下来一行包含 $n-1$ 个整数 $p_1, \dots, p_{n-1}$。对于每个 $1 \le i \le n-1$，节点 $i$ 在 $F_0$ 中的父节点为 $p_i$。满足 $p_i < i$。在树中，顶点的从左到右顺序与其编号的升序对应（即编号最小的子节点是最左侧的子节点）。

输入的第三行包含一个整数 $0 \le k < 2^{30}$。接下来一行包含一个整数 $q$，$1 \le q \le 100\,000$，表示查询次数。最后有 $q$ 行，每行包含一个查询。每个查询由两个不同的整数 $a$ 和 $b$ 给出，它们是 $F_k$ 中两个顶点的标签。你可以假设 $a$ 和 $b$ 是有效的标签（即它们在 1 到 $F_k$ 的顶点数之间），并且它们最大为 $2^{30}$。

输出格式

对于每个查询 $(a, b)$，按照输入中给出的顺序，输出 $F_k$ 中标签为 $a$ 和 $b$ 的顶点之间的距离。

样例

输入 1

4
0 1 0
1
10
1 2
1 4
1 6
1 8
1 10
5 10
6 8
9 3
7 10
8 9

输出 1

1
3
3
2
2
6
5
5
1
1