Cho một dãy số nguyên, đếm số lượng dãy con liên tiếp có tổng là số nguyên tố. Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hai dãy con đó trong dãy đã cho là khác nhau. Ví dụ dãy ~2, 3, 4~; có 4 dãy con thỏa mãn là ~(2), (3), (2,3), (3,4)~.

Yêu cầu: Đếm số lượng dãy con liên tiếp có tổng là số nguyên tố.

Input

• Dòng đầu chứa một số nguyên dương ~N~ (~N \le 10^4~).
• Dòng thứ 2 chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ (~a_i \le 10^3~).

Output

• Ghi ra kết quả của bài toán.