link: http://www.codechef.com/problems/LEVY/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int A[n],i;
for(i=2;i<n;i++)//sieve_start
{
A[i]=i;
}
int p;
for(p=2;p<n;p++)
{
if(A[p]!=0)
{
for(i=p;i*p<n;i++)
{
A[i*p]=0;//'0'->not prime
}
}
}//sieve_end
int prime[n];//storing all primes in prime[].
int j=0;
for(i=2;i<n;i++)
{
if(A[i]!=0)
{
prime[j++]=i;
}
}
int a,b,count[10001];
for(i=0;i<10001;i++)
count[i]=0;
for(a=0; a<j; a++)//j=number_of_primes
{
for(b=0;b<j;b++)
{
if(prime[a]+2*prime[b]<=10000)
count[prime[a]+2*prime[b]]++;
}
}
printf("%d\n",count[n]);
}
return 0;
}
