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⁵), showing how many numbers are in the array. The next line contains n space-separated integers x_i (1 ≤ x_i ≤ 10¹²).

Output

Print one number: the numbers of T-Primes.

Sample

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.