Hung is an excellent student in computer science and is very interested in studying numbers in mathematics. One day, after studying prime numbers in class, he realized that there are prime numbers for which the sum of the digits of their squares results in a new integer that is still a prime number. These numbers are called perfect prime numbers, and the others are called imperfect prime numbers (prime numbers whose square's digit sum is not a prime number).

When Hung returned home, he quickly opened his computer to explore these numbers. However, when he opened the computer, he suddenly found a strange sequence of ~N~ positive integers (called sequence ~A~) in a folder on his computer. Hung now wants to know how many perfect prime numbers and how many imperfect prime numbers there are in this sequence.

Task: Help Hung process this information.

Input

• The first line contains the number ~N~, which is the length of the sequence.
• The second line contains the sequence ~A~ consisting of ~N~ positive integers.

Output

• Output two integers: the count of perfect prime numbers and the count of imperfect prime numbers, separated by a space.

Sample Input

5  
9 7 11 13 5

Sample Output

2 2

Notes

• ~7~ is a perfect prime number because ~7^2 = 49~, and the sum of the digits is ~4 + 9 = 13~, which is a prime number.
• ~11~ is an imperfect prime number because ~11^2 = 121~, and the sum of the digits is ~1 + 2 + 1 = 4~, which is not a prime number.
• ~13~ is an imperfect prime number because ~13^2 = 169~, and the sum of the digits is ~1 + 6 + 9 = 16~, which is not a prime number.
• ~5~ is a perfect prime number because ~5^2 = 25~, and the sum of the digits is ~2 + 5 = 7~, which is a prime number.

Constraints

• ~50\%~ of the test cases have ~N ≤ 5 \times 10^3~ and ~A_i ≤ 10^4~.
• ~40\%~ of the test cases have ~N ≤ 5 \times 10^5~ and ~A_i ≤ 10^7~.
• ~10\%~ of the test cases have ~N ≤ 10^6~ and ~A_i ≤ 10^8~.