考虑一棵具有无向边的树，其中每个节点都有一个整数值。如果相邻节点的权值的最大公约数（GCD）严格大于 1，则称它们是 GCD 和谐的。

你可以将树中任意节点的值修改为任意正整数。此操作的代价等于该节点的新值，与节点的原始值无关。你可以根据需要修改任意数量的节点值，且节点值不需要唯一。

请问使树中每一对相邻节点都满足 GCD 和谐的最小总代价是多少？

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 5,000$)，表示树中的节点数。树的节点编号从 $1$ 到 $n$。

接下来的 $n$ 行，每行包含一个整数 $v$ ($1 \le v \le 100$)。这些是节点的初始值（不保证唯一），按节点编号顺序给出。

接下来的 $n - 1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$)，表示节点 $a$ 和 $b$ 之间的一条树边。保证这些边构成一棵树。

输出格式

输出一个整数，表示使树中每一对相邻节点都满足 GCD 和谐的最小总代价。

样例

输入 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