prim007

#include <iostream>
#include <bitset>
#define N 20001
using namespace std;
bitset <N> prim;

void Ciur() /// Ciurul lui Eratostene
{
	prim[0]=prim[1]=1;
	for(int i=2;i*i<N;++i)
		if(prim[i]==0)
			for(int j=2;i*j<N;++j)
				prim[i*j]=1;
}

int F[10001];
long long sume_prim()
{
    long long sol=0;
    for(int i=0;i<=10000;i+=2) /// i par
        for(int j=1;j<=9999;j+=2) /// si j impar
            if(!prim[i+j]) /// pentru ca doar asa suma poate fi nr prim (cu mici exceptii)
                sol+=F[i]*F[j];
    if(F[1]>1)
        sol+=F[1]*(F[1]-1LL)/2LL; /// Luam in calcul si 1+1
    sol+=F[0]*F[2]; /// Luam in calcul si 0+2
    return sol;
}

int main()
{
    Ciur();
    int n,x;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>x,++F[x];
    cout<<sume_prim()<<'\n';
    return 0;
}