J4 - Soup and Sexy Primes

Soup has recently learned about the concept of sexy primes. He has recently tasked you with writting a program that will output the number of pairs of sexy primes in a given array.

Constraints

$2 \leq N \leq 10^6$

$0 \leq a_i \leq 2\cdot10^5$

$2 \leq N \leq 10^3$

$0 \leq a_i \leq 10^3$

No further constraints.

Input Specification

The first line of input contains the integers $N$, denoting the number of integers in the array

The following line contains $N$ integers, each denoting an element $a_i$ in the array.

Output Specification

Ouput a single integer denoting the number of pairs of sexy primes we can create using all the numbers in the array.

Sample Input

5
5 11 17 41 47


Sample Output

3


Sample Explanation

The pairs of sexy primes are: $(5, 11), (11, 17), (41, 47)$

Sample Input

6
5 5 5 11 11 11


Sample Output

9


Sample Explanation

We can make 9 pairs of the form $(5,11)$, since each of the 3 $5$s can be matched with each of the 3 $11$s