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?

Input

• Dữ liệu được đọc từ file văn bản SODEP.INP.
• 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 kết quả ra file văn bản SODEP.OUT.

Scoring

Example input 1

9
9 7 10 6 17 4 19 21 23

Example output 1

5

Note 1

• Các số ~10~, ~6~, ~4~, ~21~ là các số đẹp.