给定一个长度为 $$$n$$$ 的数组 $$$a$$$,它有一个特殊条件:该数组中的每个元素最多有 7 个除数。求该数组乘积的最短非空子序列的长度,其元素是完全平方数。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是数组 $$$b$$$ 的子序列。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_{n}$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。
输出
输出 $$$a$$$ 的乘积的最短非空子序列的长度,其元素是完全平方数。如果有几个最短子序列,则可以找到其中任何一个。如果没有这样的子序列,则打印“-1”。
示例
输入 #1
3 1 4 6
输出 #1
1
输入 #2
4 2 3 6 6
输出 #2
2
输入 #3
3 6 15 10
输出 #3
3
输入#4
4 2 3 5 7
输出#4
-1
注意
在第一个示例中,您可以选择子序列$$$[1]$$$。
在第二个示例中,您可以选择子序列 $$$[6, 6]$$$。
在第三个示例中,您可以选择子序列 $$$[6, 15, 10]$$$。
在第四个样本中,没有这样的子序列。