Dãy con

Cho một dãy số gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) có giá trị không vượt quá \(10^6\). Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai phần tử là số nguyên tố.

Input

Dữ liệu vào:

• Dòng đầu tiên gồm một số nguyên dương \(N\) (\(N \le 10^6\)) là số lượng phần tử của dãy số;

• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) lần lượt mô tả các phần tử của dãy số.

Ràng buộc:

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(N \le 10^3\); \(a_i \le 10^3\);

• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(N \le 10^6\); \(a_i \le 10^3\);

• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.

Output

In ra

Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra \(-1\).

Example

Input:

10
3 4 8 4 5 6 1 7 4 6

Output:

4

Note

Các số nguyên tố trong dãy nằm ở vị trí \(1\) (giá trị \(3\)), vị trí \(5\) (giá trị \(5\)) và vị trí \(8\) (giá trị \(7\)). Hai số nguyên tố liên tiếp gần nhau nhất là các vị trí \(5\) và \(8\), nên chọn dãy con từ vị trí thứ \(5\) đến vị trí thứ \(8\) gồm \(5, 6, 1, 7\) có \(4\) phần tử. Cặp vị trí \(1\) và \(5\) cho dãy con dài \(5\) phần tử nên không tối ưu hơn.