Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

divide and conquer

dp

dsu

number theory

trees

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. GCD Counting

time limit per test

4.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a tree consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is equal to $$$a_i$$$.

Let's denote the function $$$g(x, y)$$$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $$$x$$$ to vertex $$$y$$$ (including these two vertices).

For every integer from $$$1$$$ to $$$2 \cdot 10^5$$$ you have to count the number of pairs $$$(x, y)$$$ $$$(1 \le x \le y \le n)$$$ such that $$$g(x, y)$$$ is equal to this number.

Input

The first line contains one integer $$$n$$$ — the number of vertices $$$(1 \le n \le 2 \cdot 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — the numbers written on vertices.

Then $$$n - 1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ $$$(1 \le x, y \le n, x \ne y)$$$ denoting an edge connecting vertex $$$x$$$ with vertex $$$y$$$. It is guaranteed that these edges form a tree.

Output

For every integer $$$i$$$ from $$$1$$$ to $$$2 \cdot 10^5$$$ do the following: if there is no pair $$$(x, y)$$$ such that $$$x \le y$$$ and $$$g(x, y) = i$$$, don't output anything. Otherwise output two integers: $$$i$$$ and the number of aforementioned pairs. You have to consider the values of $$$i$$$ in ascending order.

See the examples for better understanding.

Examples

Input

3

1 2 3

1 2

2 3

Output

1 4

2 1

3 1

Input

6

1 2 4 8 16 32

1 6

6 3

3 4

4 2

6 5

Output

1 6

2 5

4 6

8 1

16 2

32 1

Input

4

9 16 144 6

1 3

2 3

4 3

Output

1 1

2 1

3 1

6 2

9 2

16 2

144 1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 09:31:25 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|