Cho dãy số nguyên có ~n~ phần tử ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^{18}~; ~1 \le n \le 10^6~). Một dãy con của dãy số đã cho là dãy số ~a_l, a_{l+1}, \ldots, a_r~ (~1 \le l \le r \le n~). Hai dãy con được gọi là liên tiếp nếu phần tử cuối cùng của dãy thứ nhất đứng liền trước phần tử đầu tiên của dãy thứ hai trong dãy ban đầu. Ví dụ: cho dãy số 1, 2, 3, 4, 5 các dãy con liên tiếp của dãy số đã cho có thể là {1, 2}; {3, 4}; {5}. Ước chung lớn nhất của dãy con là ước chung lớn nhất của tất cả các phần tử trong dãy. Nếu dãy con chỉ có một phần tử thì ước chung lớn nhất của dãy chính là phần tử đó.

Yêu cầu: cho dãy số ~a_1, a_2, \ldots, a_n~. Hãy chia dãy số đã cho thành nhiều nhất các dãy con liên tiếp nhau sao cho ước chung lớn nhất của các dãy con đều là 1.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ là số phần tử của dãy số;
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Kết quả

Gồm một dòng chứa một số là số lượng nhiều nhất các dãy con thỏa mãn yêu cầu của bài toán. Nếu không thể chia được thì đưa ra -1.

Ví dụ

Ví dụ 1

DIVIDE.INP

5
1 3 5 7 9

DIVIDE.OUT

3

Giải thích: Cách chia thỏa mãn yêu cầu đề bài: {{1}; {3, 5}; {7, 9}}

Ví dụ 2

DIVIDE.INP

4
3 3 3 9

DIVIDE.OUT

-1

Giải thích: Không tồn tại dãy con có ước chung lớn nhất bằng 1.

Giới hạn

• Subtask 1 (20% số test): ~1 \le n \le 10^3~; ~1 \le a_i \le 10^6~ (~i = 1, 2, \ldots, n~);
• Subtask 2 (20% số test): ~1 \le n \le 10^5~; ~1 \le a_i \le 10^9~ (~i = 1, 2, \ldots, n~);
• Subtask 3 (60% số test): ~1 \le n \le 10^6~; ~1 \le a_i \le 10^{18}~ (~i = 1, 2, \ldots, n~).