Khi học về số nguyên tố, An phát hiện ra rằng có những số nguyên dương mà các ước thực sự (không kể $1$ và chính nó) của nó đều là các số nguyên tố và An đã gọi những số này là số đẹp. Ví dụ $10$ là một số đẹp vì có hai ước thực sự là $2$ và $5$ đều là các số nguyên tố. An có một người bạn rất thân vốn rất đam mê lập trình nên đã đặt ra bài toán cho bạn mình giải như sau: Cho dãy $n$ số nguyên $a_1,a_2,\ldots,a_n$ ($1 \leq n \leq 10^6$, $1 \leq a_i \leq 2\times 10^7$). Hãy cho biết trong dãy số trên có bao nhiêu số đẹp?

Yêu cầu: Hãy giúp bạn của An giải bài toán trên.

Input

Đọc từ file văn bản SODEP.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên $n$ ($1 \leq n \leq 10^6$);
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq 2\times 10^7$, $1 \leq i \leq n$). Các số cách nhau bởi dấu cách.

Output

Ghi ra file văn bản SODEP.OUT một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask 1 ($50\%$): $1 \leq n \leq 1000$, $1 \leq a_i \leq 10^4$;
• Subtask 2 ($30\%$): $1000 < n \leq 10^4$, $10^4 < a_i \leq 10^6$;
• Subtask 3 ($20\%$): $10^4 < n \leq 10^6$, $10^6 <a_i < 2\times 10^7$.

Example

9
9 7 10 6 17 4 19 21 23

5