Count the prime numbers and perfect squares in an array.

Input

The first line contains \(n\). The second line contains \(n\) non-negative integers.

The input satisfies:

• \(0 <= n <= 1000\)

Output

Print the prime count, then the perfect-square count, on separate lines.

Example

Input

6
5 1 2 4 3 11

Output

4
2