CF1043F.Make It One

Janusz is a businessman. He owns a company "Januszex", which produces games for teenagers. Last hit of Januszex was a cool one-person game "Make it one". The player is given a sequence of $n$ integers $a_i$.

It is allowed to select any subset of them, and the score is equal to the greatest common divisor of selected elements. The goal is to take as little elements as it is possible, getting the score $1$. Now Janusz wonders, for given sequence, how much elements should the player choose?

扬努什是一位商人。他拥有一家名为“扬努什克斯”（Januszex）的公司，专门面向青少年开发游戏。“扬努什克斯”最近推出的热门单人游戏名为《化一为一》（Make it one）。游戏中，玩家会得到一个长度为 $n$ 的整数序列 $a_i$。

玩家可以任选其中若干个元素组成一个子集，其得分为该子集中所有元素的最大公约数（GCD）。游戏目标是：在保证得分为 $1$ 的前提下，尽可能少地选取元素。现在扬努什想知道：对于给定的序列，玩家最少需要选取多少个元素？

The first line contains an only integer $n$ ($1 \le n \le 300\,000$) — the number of integers in the sequence.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 300\,000$).

第一行包含一个整数 $n$（$1 \le n \le 300\,000$）—— 表示序列中整数的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 300\,000$）。

If there is no subset of the given sequence with gcd equal to $1$, output -1.

Otherwise, output exactly one integer — the size of the smallest subset with gcd equal to $1$.

如果给定序列中不存在最大公约数（gcd）为 $1$ 的子集，则输出 $-1$。

否则，输出一个整数——即最大公约数为 $1$ 的最小子集的大小。

In the first example, selecting a subset of all numbers gives a gcd of $1$ and for all smaller subsets the gcd is greater than $1$.

In the second example, for all subsets of numbers the gcd is at least $2$.

在第一个例子中，选取所有数字的一个子集可得到最大公约数为 $1$，而对于所有更小的子集，其最大公约数均大于 $1$。

在第二个例子中，对于所有数字子集，其最大公约数至少为 $2$。