E. Eren's GCD Questions
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hope you have already seen the legendary anime Attack On Titan. Now, I am writing the missing plot of the anime. Inside Wall Maria, there are $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$. They are connected by $$$n-1$$$ bi-directional roads. From each city, it is possible to visit any other city by using some sequence of roads. The path from one city to another city is always unique. Each city $$$i$$$ ($$$1 \leq i \leq n$$$) has $$$a_i$$$ number of titans. One day, Eren told Mikasa "Now I will ask you some questions. In each question, you are given two cities $$$x$$$ and $$$y$$$. You have to tell in the shortest path of the given two cities, if there exists at least one pair of cities $$$i$$$, $$$j$$$ such that GCD of the number of titans of cities $$$i$$$, $$$j$$$ is greater than $$$1$$$". You have to help Mikasa by answering the questions for her. Otherwise, Eren will misbehave with her once again saying "Mikasa, you are an Ackerman".

GCD of two positive integers $$$a$$$ and $$$b$$$ is the biggest integer $$$d$$$ such that both integers $$$a$$$ and $$$b$$$ are divisible by $$$d$$$.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the number of cities.

The second line contains n integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$) — number of titans of each city.

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) denoting the bi-directional road between cities $$$u_i$$$ and $$$v_i$$$.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of questions.

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x , y \le n$$$, $$$x \neq y$$$) — the cities for each question.

Output

For each question$$$,$$$ you have to print YES if there exist at least one pair of cities having GCD greater than $$$1$$$ in the shortest path of the given cities. Otherwise, print NO.

You can output YES and NO in any case (for example$$$,$$$ strings yEs$$$,$$$ yes$$$,$$$ Yes and YES will be recognized as a positive response).

Example
Input
7
8 5 6 9 10 3 4
1 2
1 3
2 6
2 7
3 4
3 5
3
5 6
6 1
1 7
Output
YES
NO
YES
Note
For the first question, the cities in the shortest path of the city $$$5$$$ and $$$6$$$ are $$$5$$$, $$$3$$$, $$$1$$$, $$$2$$$ and $$$6$$$. There are a few ways to choose a pair of cities satisfying the above conditions. Some of them are,
  1. GCD of the number of titans of cities $$$6$$$ and $$$3$$$ is $$$GCD(a_6, a_3) = GCD(3, 6) =3$$$ which is greater than $$$1$$$.
  2. GCD of the number of titans of cities $$$3$$$ and $$$5$$$ is $$$GCD(a_3, a_5) = GCD(6, 10) =2$$$ which is greater than $$$1$$$.
  3. GCD of the number of titans of cities $$$1$$$ and $$$3$$$ is $$$GCD(a_1, a_3) = GCD(8, 6) =2$$$ which is greater than $$$1$$$.

Therefore, the answer to the first question is YES.

For the second question, the GCD of the number of titans of any pair of cities is $$$1$$$.

Therefore, the answer for the second question is NO.