题目描述

塔子哥有一棵树，树上每个结点都有一个权值，权值是 $3$ 或者 $5$ ，

现在，塔子哥想问你，对于每条路径，路径上的点的权值的最小公倍数之和是多少

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示树中结点数量。

第二行， $n$ 个整数，第 $i$ 个整数表示第 $i$ 个结点的权值 $a_i(a_i=3$ 或者 $a_i=5)$

接下来 $n-1$ 行，第 $i$ 行两个整数 $u_i,v_i(1 \leq u_i,v_i \leq n)$ 表示结点 $u_i$ 和 $v_i$ 之间有一条边。

输出描述

一个整数，表示所有路径上的点的权值的最小公倍数之和

样例

输入

3
5 3 3
2 1
3 2

输出

33

说明

路径 $1-2$ 的权值最小公倍数为：$lcm(5,3)=15$

路径 $2-3$ 的权值最小公倍数为：$lcm(3,3)=3$

路径 $1-2-3$ 的权值最小公倍数为:$lcm(5,3,3)=15$

15+15+3=33