Trong quá trình tìm ý tưởng để chuẩn bị đề thi thử kỳ chọn đội tuyển quốc gia năm 2024 – 2025, Thành đã chọn được ~N~ ý tưởng để viết đề, mỗi ý tưởng được kí hiệu bằng 1 số nguyên dương (các ý tưởng có thể kí hiệu giống nhau). Sau quá trình dầy công nghiên cứu Thành phát hiện ra cách tạo ra một đề bài hay. Cụ thể một đề bài hay là một đoạn các ý tưởng liên tiếp mà không ý tưởng nào được kí hiệu bằng một số nguyên tố.

Do sau quá trình đó, Thành đã quá mệt mỏi nên anh ấy đã nhờ bạn tìm xem có bao nhiêu đề bài hay có thể tạo ra.

Yêu cầu: Hãy đếm số lượng các đoạn con liên tiếp mà không chứa giá trị là số nguyên tố.

Input

• Dòng đầu tiên là số nguyên dương ~N~ là số lượng ý tưởng mà Thành đã tìm được (~N \le 10^5~).
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ là kí hiệu đặt cho các ý tưởng (~A_i \le 10^6, 1 \le i \le N~).

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Sample Input 1

7 
4 6 2 1 4 7 3

Sample Output 1

6