Cho dãy số ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ thỏa mãn ~a_1 + a_2 + ... + a_n \le 10^6~. Hãy đếm số đoạn con liên tiếp khác rỗng của ~a~ có tổng là số nguyên tố.

Dữ liệu

Gồm ~2~ dòng:

• Dòng đầu tiên chứa 2 số nguyên ~n~ ~(n \leq 5000)~.
• Dòng thứ 2 chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^6)~ phân tách bằng dấu cách.

Kết quả

In ra 1 số nguyên là số đoạn con liên tiếp thỏa mãn đề bài.

Sample Input

5
1 3 4 7 6

Sample Output

6

Subtask

• ~30\%~ số test có ~n \le 100, a_1 + a_2 + ... + a_n \le 500~
• ~30\%~ số test tiếp theo có ~n \le 1000~
• ~40\%~ số test còn lại không có điều kiện gì thêm