###### Category

###### Similar Problems

## 0707. T-primes

###### Time limit : 2000 ms

Memory limit : 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* ≤ 10^{5}),
showing how many numbers are in the array. The next line contains *n* space-separated integers
*x _{i}* (1 ≤

*x*≤ 10

_{i}^{12}).

Output

Print one number: the numbers of T-Primes.

Sample

№ |
Input |
Output |

1 |
3 |
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.

Text from: codeforces.ru