The brain-eating Cthulhu universe, the mysterious Wisdom Tree—it all just began...

The immortal Wisdom Tree is a rooted tree consisting of $n$ nodes and $n-1$ edges, with node 1 as the root. Each node $i$ in the Wisdom Tree has a fruit with a value $a_i$.

To destroy the core of the Wisdom Tree, the protagonist Tang Xiaoyi will make several trips. He possesses a special backpack to carry fruits during his travels. The backpack has the following properties:

• The values of the fruits in the backpack are distinct.
• Initially, the backpack only contains the fruit corresponding to the starting node.
• Tang Xiaoyi can add a fruit with value $x$ to the backpack if and only if the backpack already contains a fruit with value $x-1$.

Given $q$ travel routes for Tang Xiaoyi, where each route starts at $s$ and ends at $t$, with the guarantee that $t$ is an ancestor of $s$. Assuming Tang Xiaoyi travels strictly along the simple path from $s$ to $t$, help him calculate the maximum number of fruits he can collect.

Note: Due to the immense power of the Wisdom Tree's core, once fruits are taken, they are immediately replaced by new fruits of the same value, meaning the $q$ trips are independent and do not affect each other.

Input

The first line contains an integer $n$ ($1 \le n \le 10^6$), representing the number of nodes in the Wisdom Tree. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$), representing the value of the fruit at each node. The third line contains $n-1$ integers $f_i$ ($1 \le f_i \le n$), representing the parent of each node $i$ (where $i$ ranges from 2 to $n$), ensuring the structure is a tree. The fourth line contains an integer $q$ ($1 \le q \le 5 \times 10^5$), representing the number of trips Tang Xiaoyi makes. The following $q$ lines each contain two integers $s, t$ ($1 \le s, t \le n$), representing the start and end nodes of the current trip, ensuring $t$ is an ancestor of $s$.

Output

Output $q$ lines, where the $i$-th line contains the answer for the $i$-th trip: the maximum number of fruits Tang Xiaoyi can collect during that trip.

Examples

Input 1

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

Output 1

1
3

Note

For the first query, the backpack can only contain the fruit with value 2 from the starting node. For the second query, the backpack can contain fruits along the path with values 3, 4, and 5.