一棵树有 n 个节点，n-1 条边。第 i 条边连接的两个结点是 u[i]和 v[i]。第 i 个结点有一个权值 a[i]。对于任意的 1<=i<j<=n，给出一些定义：

1、定义 Path[i][j]表示结点 i 到结点 j 的简单路径上的所有结点的集合。

2、定义 gcd[i][j]表示 Path[i][j]集合内所有结点的权值的最大公约数。

3、定义 size[i][j]表示结点 i 到结点 j 的简单路径所包含的结点数量（包含结点 i 和 j)。

4、定义 cost[i][j] = size[i][j] × gcd[i][j]。

你的任务是：对于任意的 1<=i<j<=n，求 cost[i][j]的总和，则求：

第一行，一个整数 n。

第二行，n 个整数，第 i 个整数是 a[i]。

接下有 n-1 行，第 i 行是两个整数 u[i]和 v[i]，1<= u[i]<v[i]<=n, 表示树的第 i 条边。

一个整数。

【输入样例 2】

10

180 168 120 144 192 200 198 160 156 150

1 2

2 3

2 4

2 5

5 6

4 7

7 8

7 9

9 10

【输出样例 2】

【数据范围】

对于 50%的数据， 1<=n<=1000,

1<=a[i]<=100000。