Problem F
Fractal Tree

A fractal tree $F_ i$ is defined in the following way. First, a rooted tree $F_0$ is given, which contains at least 2 vertices. $F_ i$ is then defined recursively in the following manner. Consider the set of vertices $S$ which are leaves in $F_{i-1}$. For each vertex $v$ in $S$, we replace it with a copy of $F_0$, such that $v$ corresponds to the root of $F_0$.

Now, consider the tree $F_ k$, for a given $k$. In this tree, we perform a depth-first search, where we visit all vertices of the tree recursively. At a certain vertex, we first recurse into the subtree of the leftmost child of the vertex, then the second leftmost child, and so on, until we have visited all the vertices in the subtree of the vertex. Assign integer labels to the vertices in the order they were visited, starting at $1$. See Figure 1 for an example.

(a) The tree $F_0$.

  

(b) The tree $F_1$.

  

(c) The depth first search labelling of $F_1$.

Figure 1: Illustration of Sample Input 1.

Given a set of queries consisting of pairs of vertices, your task is to find the distance between the two vertices. The distance is defined as the number of edges on the (unique) simple path between the two vertices.

Input

First, the tree $F_0$ is given. The first line of input contains the number of vertices $2 \le n \le 100\, 000$ in $F_0$. The vertices are numbered $0$ to $n - 1$, with $0$ being the root vertex. Then follows a line containing $n-1$ integers $p_1, \ldots , p_{n-1}$. For each $1 \le i \le n-1$, the parent of node $i$ in $F_0$ is $p_ i$. It holds that $p_ i < i$. Within the tree, the left-to-right ordering of the vertices correspond to their numbering, in ascending order (i.e. the lowest-numbered child is the leftmost child).

The third line of input contains an integer $0 \le k < 2^{30}$. Then follows a line containing an integer $q$, $1 \le q \le 100\, 000$, the number of queries. Finally, there are $q$ lines containing the queries. Each query is given by two distinct integers $a$ and $b$, the labels of two vertices of $F_ k$. You may assume that $a$ and $b$ are valid labels (i.e., they are between $1$ and the number of vertices of $F_ k$), and that they are at most $2^{30}$.

Output

For each query $(a, b)$, in the same order as given in the input, output the distance in $F_ k$ between the vertices labelled $a$ and $b$.

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
3
3
2
2
6
5
5
1
1