## 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 ≤ 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.