There is a tree (an undirected connected graph with no cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Each vertex has a weight.

Write a program that processes the following query:

• u v: Print the number of distinct weights of vertices on the path from $u$ to $v$.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$).

The second line contains the weights of the vertices in order from vertex $1$ to vertex $N$.

The next $N-1$ lines each contain two integers $u$ and $v$ that an edge connects.

The next line contains $M$ ($1 \le M \le 100{,}000$), the number of queries.

The next $M$ lines each contain one query.

The weight of each vertex is a natural number not exceeding $1{,}000{,}000$.

Output

For each query, output the result in order, one per line.

Examples

Input 1

8
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2
2 5
7 8

Output 1

4
4