使最大公因数为一

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个含 $n$ 个正整数的序列。你可以选择任意非空下标子集，得分为所选数的最大公因数。

求为了使得分为 $1$，至少需要选择多少个数；若无法做到，输出 $-1$。

输入格式

第一行一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出最少选择个数，无法使最大公因数为 $1$ 时输出 $-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\le n\le300000$，$1\le a_i\le300000$。