You are given a rooted tree consisting of $n$ vertices. The vertices of the tree are numbered by integers from $1$ to $n$. The parent of vertex $v$ is represented as $par_v$. The root of the tree is a vertex with number $1$.

You are required to answer $q$ queries. Each query is described by two integers $v_j$ and $u_j$. The answer to query $v_j$, $u_j$ is the minimum number of attempts for reaching the vertex $u_j$ from $v_j$. You can perform one of the following operations per attempt:

• Traverse to a neighbor of the current vertex.
• Traverse to the $({2^k})^{th}$ parent of current vertex where $k$ is a non-negative integer.
• If the current distance with the root is an even number, going to the vertex in the path between me and root where the distance of those vertex with me and root is equal.

Input format

• First line: An integer $n$ denoting the number of nodes in the tree ($1 \le n \le 5000$)
• Next line: $n − 1$ space-separated integers where the $i^{th}$ integers is $par_i$ and it denotes the parent of vertex $i$ ($1 \le par_i < i$)

Output format

For each query, print the minimum number of attempts to reach from the first node to the second node.