每个人都有其独特的能力，对于第 $i$ 个人，令 $a_i$ 表示他/她的能力值。对于第 $i$ 个人和第 $j$ 个人，我们假设他们能够和睦相处当且仅当 $\gcd(a_i, a_j) \neq 1$。

我们认为一个团队是和谐的，如果它满足以下条件：

• 一个和谐的团队应包含不少于 $3$ 名员工。
• 在一个包含 $m$ 名员工的和谐团队中，能力值第 $i$ 高的人将与能力值第 $i-1$ 高和第 $i+1$ 高的人合作。
• 注意，能力值最高（第 $1$ 高）的人仅与能力值第二高的人合作。同样地，能力值第 $m$ 高（即最低）的人仅与能力值第 $m-1$ 高的人合作。
• 最重要的是，每位成员都必须与所有和他/她合作的人和睦相处。

现在，凯特是一家拥有 $n$ 名员工的公司的老板，这些员工的能力值两两不同。她希望你组建一个最大的和谐团队，并输出该团队中的员工人数。如果无法组建这样的团队，则输出 -1。

输入格式

第一行包含一个整数 $n$（$3 \le n \le 3 \times 10^5$），表示凯特公司的员工人数。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^5$），分别表示第 $i$ 个员工的能力值。

输出格式

输出仅一行，包含一个整数，表示最大和谐团队中的员工人数。如果不存在这样的团队，则输出 -1。

样例

输入样例 1

5
19 15 5 1 12

输出样例 1

-1

输入样例 2

10
2 7 18 3 9 11 5 12 17 20

输出样例 2

5