Problem Description

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?

Input Format

The first line of input contains a single integer $n$ ($2 \le n \le 5{,}000$), which is the number of nodes in the tree. Tree nodes are numbered from 1 to $n$.

Each of the next $n$ lines contains an integer $v$ ($1 \le v \le 100$). These are the initial values of the nodes (which are not guaranteed to be unique), in node number order.

Each of the next $n - 1$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n, a \ne b$), indicating a tree edge between nodes $a$ and $b$. It is guaranteed that these edges form a tree.

Output Format

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

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

6

3
1
2
3
3 1
2 3

4