C. Coprime Pairs
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, rooted at vertex $$$1$$$. Vertex $$$i$$$ has a positive integer $$$a_i$$$ written on it.

For every vertex $$$x$$$, count the unordered pairs of distinct vertices $$$u$$$ and $$$v$$$ in the subtree of $$$x$$$ such that $$$\gcd(a_u,a_v)=1$$$.

The subtree of $$$x$$$ includes $$$x$$$ and all its descendants; $$$\gcd$$$ denotes the greatest common divisor.

Input

The first line contains an integer $$$n$$$ ($$$1\le n\le 10^5$$$), the number of vertices.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^5$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$, $$$u_i\ne v_i$$$), the endpoints of an edge. The edges form a tree. They may be listed in any order; vertex numbers do not specify the parent-child relationship.

Output

Print the answer for each vertex from $$$1$$$ to $$$n$$$, one per line.

Examples
Input
8
6 1 10 1 15 7 6 14
1 2
1 3
2 4
2 5
3 6
6 7
6 8
Output
18
3
2
0
0
1
0
0
Input
3
6 10 15
1 2
2 3
Output
0
0
0
Input
4
1 1 1 1
1 3
3 2
2 4
Output
6
1
3
0
Note

In the first example, the subtree of vertex $$$2$$$ has values $$$1,1,15$$$, so all three pairs qualify. The subtrees of vertices $$$3$$$ and $$$6$$$ have two and one suitable pairs, respectively.

In the second example, $$$\gcd(6,10,15)=1$$$, but no pair of values is coprime.

In the third example, the subtree sizes are $$$4,2,3,1$$$; every pair of distinct vertices qualifies.