Cho số nguyên dương ~N~ và dãy ~a~ gồm ~N~ số nguyên dương ~a_1, a_2,..., a_N~.

Một dãy được gọi là dãy con của ~a~ nếu nó được tạo ra bằng cách lấy ra ~k~ phần tử liên tiếp trong ~a~ ~(k \ge 1)~.

Yêu cầu

Tìm dãy con dài nhất của ~a~ sao cho tất cả các phần tử trong dãy đều là số nguyên tố.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương ~N~ ~(1 \le N \le 10^5)~ là số lượng phần tử của dãy ~a~.
• Dòng thứ hai ghi dãy ~a~ gồm ~N~ số nguyên dương ~a_1, a_2,..., a_N~ ~(1 \le a_i \le 10^6;\ 1 \le i \le N)~, các số được ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên ~t~ duy nhất là độ dài của dãy con tìm được theo yêu cầu. Trường hợp không tồn tại dãy con nào thỏa mãn thì ghi số ~0~.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm: ~N \le 10^3;\ a_i \le 10^3~
• Có 40% số test ứng với 40% số điểm: không có ràng buộc gì thêm

Ví dụ

Ví dụ 1

INPUT

6
1 5 2 3 4 5

OUTPUT

3

Ví dụ 2

INPUT

6
1 4 8 9 12 6

OUTPUT

0