Do có thành tích cao trong học tập, Hùng được các mạnh thường quân thưởng rất nhiều phần quà. Để tăng phần hấp dẫn các mạnh thường quân để các phần thưởng trong các hộp được đánh số, hộp có phần thưởng là hộp được kí hiệu bằng một số nguyên tố nào đó (một số nguyên dương được gọi là một số nguyên tố khi nó chỉ có 2 ước số là 1 và chính nó), các hộp còn lại không kí hiệu bằng các số nguyên tố thì không có phần thưởng. Thấy số lượng hộp quá nhiều, Hùng hồi hộp không biết mình nhận được bao nhiêu phần thưởng từ các hộp kia. Em hãy lập trình đếm xem Hùng có thể nhận được bao nhiêu hộp có phần thưởng.

Input

• dòng thứ nhất chứa số nguyên dương \(n\).
• dòng tiếp theo chứa n số nguyên dương \(a_1, a_2, …, a_n\) các số cách nhau một dấu cách, dãy số \(a_1, a_2, …, a_n\) là dãy các số kí hiệu của các hộp.

Output

• Một số duy nhất là kết quả tính được

Scoring

• 50% test tương ứng với 50% số điểm của bài, ứng với \(n ≤ 10^{3}\), \(a_i ≤ 10^{3}\).
• 30% test tương ứng với 30% số điểm của bài, ứng với \(n ≤ 10^{4}\) \(a_i ≤ 10^{4}\).
• 20% test tương ứng với 20% số điểm của bài, ứng với \(n≤ 10^{6}\), \(a_i ≤ 10^{6}\).

Example

6
1 2 3 5 8 9

3