Xoá để ước chung là một

Cho dãy \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\). Bạn có thể xoá một số phần tử bất kỳ khỏi dãy (nhưng dãy còn lại phải khác rỗng). Sau khi xoá, tính ước chung lớn nhất (GCD) của tất cả phần tử còn lại.

Hãy tìm số phần tử ít nhất cần xoá để GCD của các phần tử còn lại bằng \(1\). Nếu không thể, in ra \(-1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, \dots, a_n\).

Output

In ra một số nguyên là đáp án.

Constraints

• \(1 \le n \le 10^5\).
• \(1 \le a_i \le 10^9\).

Sample Input 1

3
6 10 15

Sample Output 1

0

Sample Input 2

3
12 18 30

Sample Output 2

-1

Explanation

Ví dụ 1: \(\gcd(6, 10, 15) = 1\) nên không cần xoá. Ví dụ 2: mọi phần tử đều chia hết cho \(6\) nên GCD của bất kỳ tập con nào cũng là bội của \(6\), không thể bằng \(1\).