Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714622

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177

So'ngi izohlar

707. T-primes
Vaqt limiti: 2 sekund
Xotira limiti: 64 MB

We know that prime numbers are positive integers that have exactly two distinct positive divisors. Similarly, we'll call a positive integer t Т-prime, if t has exactly three distinct positive divisors.

You are given an array of n positive integers. Determine the numbers of T-primes among them.

Input

The first line contains a single positive integer, n (1 ≤ n ≤ 105), showing how many numbers are in the array. The next line contains n space-separated integers xi (1 ≤ xi ≤ 1012).

Output

Print one number: the numbers of T-Primes.

Sample

 № Input Output 1 ```3 4 5 6``` `1`

Note:

4 has exactly three divisors — 1, 2 and 4. It is T-Prime.

5 has two divisors (1 and 5). It is not T-Prime.

6 has four divisors (1, 2, 3, 6). It is not T-Prime.