Janusz 是一名商人。他拥有一家“Januszex”公司,该公司为青少年制作游戏。 Januszex 的最后一款热门游戏是一款很酷的单人游戏“Make it one”。玩家被给予 $$$n$$$ 整数 $$$a_i$$$ 序列。
允许选择其中的任意子集,得分等于所选元素的最大公约数。目标是采用尽可能少的元素,获得分数 $$$1$$$。现在 Janusz 想知道,对于给定的序列,玩家应该选择多少元素?
输入
第一行仅包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$) — 序列中整数的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300\,000$$$)。
输出
如果给定序列中不存在 gcd 等于 $$$1$$$ 的子集,则输出 -1。
否则,输出正好一个整数——gcd等于$$$1$$$的最小子集的大小。
示例
输入 #1
3 10 6 15
输出 #1
3
输入 #2
3 2 4 6
输出 #2
-1
输入 #3
7 30 60 21 42 70 15 30
输出 #3
3
注意
在第一个示例中,选择所有数字的子集给出 $$$1$$$ 的 gcd,并且对于所有较小的子集,gcd 大于 $$$1$$$。
在第二个示例中,对于所有数字子集,gcd 至少为 $$$2$$$。