题目内容

给定一棵树，每个节点都有一个权值以及最开始是白色。

定义操作A：

选择两个有边直接相连的节点，可以将两个节点同时染红.当且仅当 他们都是白色

但是这样的题目太过简单，所以我们定义一个更复杂的操作B：

在满足操作$A$的条件下 两个节点的权值的乘积也需要是$x * x$的形式 ， $x \geq 1$

现在允许执行操作若干次操作B。问这棵树最多能够得到红色节点?

输入描述

第一行输入一个正整数$n$，代表节点的数量。

第二行输入$n$个正整数$a_i$，代表每个节点的权值。

接下来的$n-1$行，每行输入两个正整教$u,v$，代表节点$u$和节点$v$有一条边连接

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^9$

$1 \leq u,v \leq n$

输出描述

输出一个整数表示最多可以染红的节点数量。

样例1

输入

3
3 5 7
1 2
2 3

输出

0

样例2

输入

3
5 5 5
1 2
2 3

输出

2

说明

可以染红第二个和第三个节点。或者可以染红第一个和第二个节点。这样都是染红两个节点。

而根据规则，你无法同时染红1,2,3节点。