Đoạn con nguyên tố

Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước số là 1 và chính nó.

Cho một dãy số nguyên gồm \(n\) phần tử \(a_1, a_2, \dots, a_n\).

Yêu cầu: Hãy tìm đoạn con có các phần tử liên tiếp là số nguyên tố trong dãy số trên sao cho nó có số phần tử là lớn nhất.

Input

Dữ liệu vào: từ tệp văn bản DCNT.INP có cấu trúc:

• Dòng thứ nhất ghi số tự nhiên \(n\) (\(0 < n \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^7\)), các số cách nhau một dấu cách.

Output

Dữ liệu ra:
Ghi vào tệp DCNT.OUT duy nhất một số là độ dài đoạn con tìm được theo yêu cầu.

Example

6
1 5 3 2 7 4

4

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài có \(n \le 10^3\), \(|a_i| \le 10^3\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài có \(n \le 10^4\), \(|a_i| \le 10^6\).
• Có \(40\%\) số test khác ứng với \(40\%\) số điểm với trường hợp còn lại.