I. Will you accept Basharo challenge?
time limit per test
3 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$\textit{Basharo}$$$ is too much into counting problems and he challenge you to solve this one.

You'll be given a connected undirected graph of $$$n$$$ vertices and $$$n-1$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$ and the vertex with the number $$$i$$$ is colored with the color $$$c_i$$$. The edges are also numbered from $$$1$$$ to $$$n-1$$$.

The path from a vertex $$$u$$$ to a vertex $$$v$$$ is called beautiful if it satisfies these conditions:

  • $$$u \lt v$$$
  • $$$gcd(c_u,c_v) = 1$$$. Where $$$gcd(x,y)$$$ is the greatest common divisor of the numbers $$$x$$$ and $$$y$$$.

Your task is to count for each edge $$$i$$$ the number of beautiful paths that contain this edge.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 5\times10^4$$$) $$$-$$$ the number of vertices in the graph.

The second line contains $$$n$$$ space separated integers $$$c_1,c_2,\dots,c_n$$$ ($$$1\le c_i\le 3\times10^4$$$). $$$c_i$$$ is the color of the vertex number $$$i$$$.

The next $$$n-1$$$ lines contain the edges of the graph. The $$$i^{th}$$$ line describes the edge number $$$i$$$. Each line will contain two space-separated integers $$$x$$$ and $$$y$$$ denoting an edge between vertex number $$$x$$$ and vertex number $$$y$$$. ($$$1\le x,y\le n$$$)

Output

Print exactly $$$n-1$$$ space-separated integers where $$$i^{th}$$$ of them is the answer for the $$$i^{th}$$$ edge (The number of beautiful paths that contain this edge).

Examples
Input
4
3 2 2 2
1 2
1 3
2 4
Output
2 1 1
Input
7
35 210 14 6 21 10 15
1 2
2 3
2 4
2 5
4 6
4 7
Output
1 1 3 1 1 1
Note

in the second example beautiful paths are: (1,4) , (5,6) , (3,7). we can see that all paths contains the third edge. otherwise all edges will be included only in one beautiful path.