smoothie-web Problems Contests Ranking About
Login Register

J4 - Soup and Sexy Primes

data_usage Points
7
timer Time Limit
linear_scale Memory Limit
Created
1606250489227

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:

2N106 2 \leq N \leq 10^6

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

Subtask 1 [50%]

2N103 2 \leq N \leq 10^3

0ai103 0 \leq a_i \leq 10^3

Subtask 2 [50%]

No further constraints.

Input Specification

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

The following line contains NN integers, each denoting an element aia_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)(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)(5,11), since each of the 3 55s can be matched with each of the 3 1111s