Count Prime Squares

You are given a list of integers. Your task is to count how many numbers in the list are perfect squares of prime numbers. In other words, for a given number n in the list, check if there exists a prime p such that $$n = p^2$$.

For example, if n = 4, then p = 2 and since 2 is a prime number, 4 is counted. Conversely, if n = 10, then it cannot be represented as the square of any prime.

inputFormat

The first line of input contains a single integer k indicating the number of integers in the list. The second line contains k space-separated integers.

outputFormat

Output a single integer representing the count of numbers that are the perfect squares of prime numbers.

5
4 10 25 16 9

3