题意描述

给定 $n$ 个节点的树，初始每个节点有权值 $v_i$。

两个有直接连边的人是朋友，但是对于边 $(x,y)$，如果 $\gcd(v_x,v_y)=1$，那么他们的友谊是不牢固的。

为了让大家核邪铀碍，你可以修改某些点的权值，每次修改你可以任选一个节点并把它的权值改为任意值 $x$，同时耗费 $x$ 的代价。

你可以进行任意次修改，求使得任意有直接连边的两点 $(x,y)$ 都有 $\gcd(v_x,v_y)>1$ 的最小代价。

输入格式

第一行一个正整数 $n$，表示树的节点个数。

接下来的一行 $n$ 个正整数，第 $i$ 个数表示 $v_i$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示一条树边。保证整棵树连通。

输出格式

一行一个正整数，表示最小代价。

样例输入

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

样例输出

6

数据范围及提示

对于所有数据，有 $n,\max v_i \leq 1000$。

• subtask1（$10\text{pts}$）：满足 $n,\max v_i\leq 10$。
• subtask2（$30\text{pts}$）：满足 $n,\max v_i\leq 100$。且整棵树是一条 $1\to 2\to\cdots\to n$ 的链。
• subtask3（$60\text{pts}$）：无特殊性质。