Cho \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\).

Yêu cầu: Hãy kiểm tra xem có tồn tại cách chọn một số các phần tử của dãy sao cho chúng có \(𝐺𝐶𝐷\) bằng 1 không. Nếu có, in ra số phần tử nhỏ nhất cần chọn. Nếu không, in ra −1.

Input

• Dòng 1 chứa số nguyên \(n\) (\( 1 ≤ n ≤ 3 ∗ 10^5\) )

• Dòng 2 chứa \(n\) số nguyên \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) (\( 1 ≤ a_i ≤ 3 ∗ 10^5\) )

Output

• Ghi số lượng phần tử nhỏ nhất của tập chọn một số các phần tử của dãy sao cho chúng có \(𝐺𝐶𝐷\) bằng 1. Nếu không có ghi \(-1\).

Sample Input

5
26 28 30 18 17

Sample Output

2

Ràng buộc

• Subtask 1: \( n ≤ 20\)

• Subtask 2: \( n ≤ 100\)

• Subtask 3: \( n ≤ 3 ∗ 10^5\)