#519. 「多校联考 Round 1」Scientia

内存限制:512 MiB 时间限制:2000 ms 输入文件:scientia.in 输出文件:scientia.out
题目类型:传统 评测方式:文本比较
上传者: Woshiluo

题目描述

woshiluo 从董事长的秘书得到了董事长在活动时的行程。

为了寰宇集团的美好未来,董事长的安全至高无上。但为了合理安排,董事长的行程必须有人知道。

现在有 个工作人员,每个工作人员有一个编号,保证这个编号的因数不超过 个。

定义一个合法的行程分发方案是被分发到的工作人员的编号的乘积为完全平方数。

为了董事长的安全,现在希望最少的工作人员被分发到。

woshiluo 需要监督活动环境布置,所以设计分配方案的任务到了您手上。

输入格式

第一行一个整数

第二行 个整数,表示每个工作人员编号。

输出格式

如果有解,输出最小合法分配方案的人数。

如果无解,输出 -1

样例

样例 1:

scientia1.in:

3
1 4 6

scientia1.ans:

1

样例 2:

scientia2.in:

4
2 3 6 6

scientia2.ans:

2

样例 3:

scientia3.in:

3
6 15 10

scientia3.ans:

3

样例 4:

scientia4.in:

4
2 3 5 7

scientia4.ans:

-1

数据范围与提示

对于 的数据, 保证

对于 的数据, 保证

对于 的数据, 保证