Hôm nay Rotund được học về tính chia hết. Như thường lệ, cậu bé lại viết ra 1 dãy các số ngẫu nhiên và xem chúng chia hết cho những số nào. Không thoả mãn khi chỉ xét tính chia hết với từng số đơn lẻ, Rotund muốn nâng độ khó lên để luyện tập: với dãy số ngẫu nhiên được viết ra, cậu muốn xét tính chia hết của tích các đoạn con liên tiếp. Vì phép chia rất khó, cậu mới chỉ thành thạo khi thực hiện phép chia cho các số có 1 chữ số, nên Rotund sẽ cố gắng tìm ra các đoạn con liên tiếp có tích chia hết cho toàn bộ các số nguyên dương chỉ có 1 chữ số.

Biết rằng, tích một dãy số là tích của tất cả các phần tử thuộc dãy đó.

Yêu cầu

Đưa ra độ dài của dãy con liên tiếp ngắn nhất có tích thoả mãn nhu cầu của Rotund. Nếu không có dãy con nào thoả mãn, in ra -1.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1≤n≤10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1≤a_i≤10^9, 1≤i≤n)~.

Output

Một dòng duy nhất chứa kết quả bài toán.

Sample Input 1

10
18 10 5 15 18 20 17 14 18 10

Sample Output 1

3

Giải thích

Chọn dãy con [14, 18, 10] có độ dài là 3.

Sample Input 2

10
1 2 3 4 5 6 7 8 9 560

Sample Output 2

2

Giải thích

Chọn dãy con [9, 560] có độ dài là 2.

Subtask

• Có 50% số test ứng với 50% số điểm có ~n≤1000~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.