smoothie-web Problems Contests Ranking About

# 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

For all subtasks:

$2 \leq N \leq 10^6$

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

### Subtask 1 [50%]

$2 \leq N \leq 10^3$

$0 \leq a_i \leq 10^3$

### Subtask 2 [50%]

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