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

Yêu cầu: Hãy tìm một đoạn con nguyên tố liên tiếp dài nhất (tất cả các phần tử trong đoạn con đều nguyên tố).

Input

• Dòng thứ nhất chứa số nguyên \(n(1≤n≤10^6 ). \)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (|a_i |≤10^6 ).\)

Output

• Một số duy nhất là độ dài đoạn con nguyên tố liên tiếp dài nhất.

Sample Input

11
2 9 4 100 26 20 30 11 5 7 12

Sample Output

3