Cho 1 dãy số nguyên ~ a ~ gồm ~ n ~ phần tử. Bạn có thể thực hiện thao tác như sau : chọn 2 phần tửliên tiếptrong dãy và thay 1 trong 2 phần tử đó (phần tử nào cũng được) bởi ước chung lớn nhất của 2 phần tử đó. Hãy tính số lần thực hiện thao tác trên ít nhất để làm cho tất cả các phần tử của dãy bằng 1. Nếu không thể làm cho tất cả các phần tử bằng 1 bởi thao tác trên thì in ra -1.

Input

• Dòng đầu tiên gồm số nguyên ~ n ~ ( ~ n \le 2000 ~ ).
• Dòng tiếp theo in n số nguyên của dãy  ~ a_1, a_2,..., a_{n} ~ mỗi số cách nhau 1 dấu cách ( ~ 1 \le a_{i} \le 10^6 ~) .

Output

In ra kết quả theo yêu câu bài toán.

Sample

Input #1

3
2 6 9

Output #1

4

Hint

Ở ví dụ trên, các lần thực hiện thao tác là:

• ~ (2,2,9) ~
• ~ (2,1,9) ~
• ~ (2,1,1) ~
• ~ (1,1,1) ~