Description

小 D 有一棵 $n$ 个结点的有根树，编号为 $1,2,...,n$ 。编号为 1 的结点是根。

小 D 在每个结点上写了一个数字，编号为 i 的结点上写的数字是 $a_i$。

现在小 D 想知道，有多少对二元组 $(x,y)$，满足编号为 $x$ 的结点是编号为 $y$ 的结点的祖先，且 $a_x × a_y$是完全平方数？

注意一个点不是它自己的祖先。

Format

Input

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

第二行 $n$ 个正整数，表示 $a1 ,a2,....,an$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示编号为 $x$ 和 $y$ 的点之间有一条边。

保证给出的边组成一棵树。

Output

输出一行，包含一个整数，表示符合条件的二元组个数。

Samples

4
2 3 8 12
1 2
2 3
3 4

2

5
1 4 9 16 25
1 2
2 3
3 4
4 5

10

Limitation

对于 20% 的数据，保证 1<= n <=2000。

对于另外 10% 的数据，保证每个 $a_i$ 都是完全平方数。

对于另外 10% 的数据，保证对于每个满足 2<= i <=n 的 i，i-1 和 i 之间有一条边。

对于另外 20% 的数据，保证树是随机生成的。生成方式为：对每个满足 2<= i<=n 的 i，等概率随机选择一个满足 1<= j < i 的 j，在 i 和 j 之间连一条边。

对于所有数据，保证 1 <= n <= 105，1<= $a_i$<= 106。