#216115. [ICPC 2022 NAC] GCD Harmony

Consider a tree with undirected edges, where each node has an integer value. Adjacent nodes are said to be GCD-harmonic if the greatest common divisor (GCD) of their values is strictly greater than 1.

You can modify the value of any tree node to any positive integer. The cost of this operation is equal to the new node value, regardless of the node’s original value. You can change as many node values as needed, and node values do not need to be unique.

What is the minimum total cost to make every pair of adjacent nodes in the tree GCD-harmonic?

The first line of input contains a single integer (), which is the number of nodes in the tree. Tree nodes are numbered from 1 to .

Each of the next lines contains an integer (). These are the initial values of the nodes (which are not guaranteed to be unique), in node number order.

Each of the next lines contains two integers and (), indicating a tree edge between nodes and . It is guaranteed that these edges form a tree.

Output a single integer, which is the minimum total cost to make every pair of adjacent nodes in the tree GCD-harmonic.

样例输入 1

6
5
6
3
4
9
12
1 2
1 3
1 4
1 6
3 5

样例输出 1

6

样例输入 2

3
1
2
3
3 1
2 3

样例输出 2

4