选数问题

题目限制

5000 ms 256 M

题目描述

给一个长度为 $n$ 的数组 $a$ ，数据保证每个 $a[i]$ 的约数数量不超过 $7$ ，求最少选出多少个数（同一个数不能选 $2$ 次），使得选出的数乘积为完全平方数。无解输出 $-1$ 。

输入格式

第一行输入一个整数n，表示数组长度（1≤n≤10^5）。 第二行输入n个整数 a[i]，表示每个数组元素（1≤a[i]≤10^6）。

输出格式

输出最少需要选择多少个数。

数据范围

对于 $30\%$ 的数据，有 $1 \le n \le 10, 1 \le a_i \le 10$。

对于 $45\%$ 的数据，有 $1 \le n \le 100, 1 \le a_i \le 2000$。

对于 $100\%$ 的数据，有 $1 \le n \le 10^5, 1 \le a_i \le 10^6$。

输入样例1

4

6 15 10 11

输入样例2

3

1 2 6

输出样例1

3

输出样例2

1

样例解释

样例 $1$ 选择 $6, 15, 10$

样例 $2$ 选择 $1$ 。