Đoạn đường quốc lộ ~n~ trạm đèn giao thông liên tiếp.

Mỗi trạm đèn giao thông được gán một số ~k~. Được biết khi đèn chuyển sang màu đỏ thì sẽ bắt đầu đếm ngược từ ~k~ trở về ~0~.

Khi thiết kế đoạn đường này, chính quyền sở tại đã muốn làm trải nghiệm đi đường của người dân là tốt nhất. Chính vì thế, họ mong có thể thiết kế sao cho hai trạm đèn giao thông liên tiếp luôn có thể chuyển màu xanh cùng lúc. Được biết điều này chỉ khả thi khi số đếm ~k~ trên hai đèn liên tiếp không nguyên tố cùng nhau.

• Chính quyền muốn tìm một đoạn đường dài nhất sao cho giữa hai trạm đèn giao thông liên tiếp luôn có thể chuyển màu xanh cùng lúc.
• Cụ thể hơn, chính phủ muốn tìm một đoạn đèn giao thông ~[i, j]~ có độ dài lớn nhất (~1 \leq i \leq j \leq n~) sao cho nếu ~j > i~ thì ~\forall l \in [i, j - 1]: GCD(k_l, k_{l + 1}) \ne 1~.

Yêu cầu:

Tìm đoạn đường dài nhất có các trạm đèn giao thông thỏa yêu cầu của chính phủ.

Dữ liệu (Vào từ tệp LGS.INP):

• Dòng đầu chứa số nguyên dương ~n~ (~2 \leq n \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~k_i~, các số trên cùng một dòng cách nhau bởi dấu cách (~1 \leq k_i \leq 10^9~).

Kết quả (Xuất ra tệp LGS.OUT):

• Gồm một số nguyên dương duy nhất là kết quả bài toán: số lượng trạm đèn giao thông trên đoạn đường dài nhất thỏa đề.

Ví dụ:

4
4 3 6 2

3

Subtask:

• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~n \leq 400~, ~k_i \leq 400~.
• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~n \leq 10^3~.
• ~40\%~ số test còn lại tương ứng với ~40\%~ số điểm không có ràng buộc gì thêm.