问题描述

小明是一位尽职尽责的园丁。这天他负责维护一棵树，树上有 $n$ 个结点 $1,2,…,n$，根结点为 1，结点 $i$ 的权值为 $a_i$。

他需要更改一些结点的权值为任意正整数，使得对于任意一个至少有 $2$ 个儿子结点的结点 $i$ 满足：任意两个 $i$ 的儿子结点的权值的乘积都不是完全平方数。

请问小明至少需要修改多少个结点的权值？

输入格式

输入共 $n+1$ 行。 第一行为一个正整数 $n$。 第二行为 $n$ 个由空格分开的正整数 $a_1,a_2,…,a_n$​。 后面 $n-1$ 行，每行两个正整数表示树上的一条边。

输出格式

输出共 $1$ 行，一个整数表示答案。

6
1 2 9 8 4 4
1 2
1 3
1 4
2 5
2 6

2

样例说明

其中一种方案：将结点 2，5 的权值分别修改为 3，2。

评测用例规模与约定

对于 $20\%$ 的评测用例，保证 $n≤10^3$。

对于 $100\%$ 的评测用例，保证 $n≤10^5$，$1≤a_i≤10^9$。