暂无测试数据。

在一个项目中，需要 $n$ 个人协助完成，每个人的编号为 $1\sim n$。现在有 $n-1$ 条信息，每条信息使用两个整数 $u,v$ 描述，表示编号 $u,v$ 的人之间可以通过电话相互联系，这两人每次通过电话联系需要消耗 $1$ 单位时间。这些关系使得 $n$ 个人之间可以直接或间接进行联系。

在这个项目中，每个人都有一个核心参数信息 $x_i$，如果两个人的参数信息互为质数，则表示他们两人之间的参数信息关联性非常大，需要通过电话进行交流沟通。

蒜头君需要计算出在项目关系网中所有参数互质的人相互联系需要花费的时间之和。

若 $x,y$ 互为质数，则 $x,y$ 的最大公约数等于 $1$。

输入格式

第一行输入一个正整数 $n$，表示该项目的人数；

接下来 $n$ 行，每行输入一个正整数 $x_i$，表示每个人的核心参数信息。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示编号 $u,v$ 的人可以通过电话相互联系。

输出格式

输出一个整数，表示在项目关系网中所有参数互质的人相互联系需要花费的时间之和。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 500, 1\leq x_i \leq 50$；

• 对于 $100\%$ 的数据，$1 \leq n\leq 10000, 1\leq x_i \leq 500$；

4
1
2
3
4
1 2
2 3
3 4

8