### 问题描述 蓝桥村是蓝桥王国年年的模范村，这是因为他们村的稻田每年都是优美的。 对于一块稻田来说，如果其中任意两根不同的秧苗的高度乘积均为完全平方数，该稻田被称之为优美的稻田。 蓝桥王国的稻田验收日即将到来，但现在蓝桥村还有一块插了 $N$ 根秧苗的稻田不够优美，其中第 $i$ 根秧苗的高度为 $h_i$。 作为蓝桥杯的村长，你可以发动技能拔苗助长： - 选择一个**质数** $x(2 \leq x \leq 10^6)$ ，同时将任意一株高度为 $h$ 的秧苗变为 $h \times x$。 请问你最少需要发动多少次拔苗助长才可以将该稻田变得优美。 ### 输入格式 第一行输入一个整数 $N(1 \leq N \leq 10^5)$ 表示稻田中秧苗的数量。 第二行输入 $N$ 个整数 $h_1,h_2,h_3,\cdots,h_N(1 \leq A_i \leq 10^6)$ 表示秧苗的高度。 ### 输出格式 输出一个整数表示答案。 ### 输入样例 ```text 5 1 2 3 4 5 ``` ### 输出样例 ```text 3 ```