J. Co-Primal Ancestor
time limit per test
4 seconds
memory limit per test
900 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ has an integer value $$$a_i$$$. The tree is rooted at node $$$1$$$.

You will receive $$$q$$$ queries. In the $$$i$$$-th query, you are given two integers $$$u_{\text{input}}$$$ and $$$v_{\text{input}}$$$. Your task is to determine the number of nodes $$$x$$$ satisfying:

  1. $$$x$$$ is an ancestor of both $$$u$$$ and $$$v$$$ (a node is considered an ancestor of itself).
  2. $$$\gcd(a_x, a_u) = 1$$$ and $$$\gcd(a_x, a_v) = 1$$$.

The queries are encrypted. The actual nodes for the $$$i$$$-th query are computed as:

$$$u = u_{\text{input}} \oplus \text{last}, \quad v = v_{\text{input}} \oplus \text{last},$$$

where $$$\text{last}$$$ is the answer to the previous query (assume $$$\text{last} = 0$$$ for the first query).

Input

The first line contains an integer $$$n$$$ — the number of nodes.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ — the values of the nodes.

Each of the next $$$n-1$$$ lines contains two integers $$$x, y$$$, denoting an edge of the tree.

The next line contains an integer $$$q$$$ — the number of queries.

Each of the following $$$q$$$ lines contains two integers $$$u_{\text{input}}, v_{\text{input}}$$$.

Constraints

  • $$$1 \le n \le 5 \times 10^4$$$
  • $$$1 \le a_i \le 5 \times 10^4$$$
  • $$$1 \le x, y, u, v \le n$$$
  • $$$1 \le q \le 5 \times 10^4$$$
Output

Print $$$q$$$ integers, each on its own line — the answer to each query.

Example
Input
5
2 3 6 5 7
1 2
1 3
3 4
3 5
3
2 4
4 5
3 3
Output
1
2
0
Note
  • Query 1: $$$u = 2 \oplus 0 = 2$$$, $$$v = 4 \oplus 0 = 4$$$. Common ancestors = $$$\{1\}$$$. Node 1 has value 2, coprime with both 3 and 5. Answer = 1.
  • Query 2: $$$u = 4 \oplus 1 = 5$$$, $$$v = 5 \oplus 1 = 4$$$. Common ancestors = $$$\{1,3\}$$$. Node 1 (value 2) coprime with 5 and 7, Node 3 (value 6) coprime with 5 and 7. Answer = 2.
  • Query 3: $$$u = 3 \oplus 2 = 1$$$, $$$v = 3 \oplus 2 = 1$$$. Answer = 0.