You 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.
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.
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.
3
1 2 3
1 2
2 3
1 4
2 1
3 1
6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5
1 6
2 5
4 6
8 1
16 2
32 1
4
9 16 144 6
1 3
2 3
4 3
1 1
2 1
3 1
6 2
9 2
16 2
144 1
Name |
---|