-----Problem Statement-----
Levy's conjecture, named after Hyman Levy, states that all odd integers greater than 5 can be represented as the sum of an odd prime number and an even semiprime. To put it algebraically, 2n + 1 = p + 2q always has a solution in primes p and q (not necessary to be distinct) for n > 2. (Source: Wikipedia)
In this problem, given a positive integer N (not necessary to be odd integer greater than 5). Your task is to calculate how many distinct ordered pairs (p, q) such that N = p + 2q, where p and q are primes.

-----Input-----
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.

Each test case consists of exactly one line containing an integer N.

-----Constraints-----
- 1 ≤ T ≤ 100000 (105)
- 1 ≤ N ≤ 10000 (104)

-----Output-----
For each test case, output the number of ordered pairs (p, q) of primes such that N = p + 2q.

-----Example-----
Input:
3
2
7
11

Output:
0
1
2

-----Explanation-----
Case #1: There are no ordered pairs (p, q) such that p + 2q = 2.
Case #2: There is only one ordered pair (p, q) = (3, 2) such that p + 2q = 7.
Case #3: There are two ordered pairs (p, q) = (7, 2), (5, 3) such that p + 2q = 11.

Difficulty: interview

Starter code:

Solutions:
isPrime=[1 for i in range(10001)]
cnt=[0 for i in range(10001)]
isPrime[0]=0
isPrime[1]=0
prime=[]
for i in range(2,10001):
 if isPrime[i]:
  prime.append(i)
  for j in range(i*i,10001,i):
   isPrime[j]=0
#print(prime)
for i in prime:
 for j in prime:
  if (i + 2*j)>10000:
   break
  else:
   cnt[i + 2*j]+=1
#print(le)
for _ in range(int(input())):
 n=int(input())
 print(cnt[n])

sieve = [False] + [True]*10000
s = []
for x in range(2,10001):
 if(sieve[x]):
  s.append(x)
  for i in range(2*x,10001,x):
   sieve[i] = False
cnt = [0]*(10001)
n = 10000
for x in s:
 for y in s:
  if(x + 2*y)>n:
   break
  cnt[x + 2*y]+=1
for _ in range(int(input())):
 n = int(input())
 print(cnt[n])

import math
MAX = 10001
PRIME=[]
A=[1 for i in range(MAX)]
A[0] = 0
A[1] = 0
B=[0 for i in range(MAX)]

for i in range(2,int(math.sqrt(MAX))+1):
 if A[i] is 1:
  for j in range(i*i,MAX,i):
   A[j] = 0
for i in range(MAX):
 if A[i] is 1:
  PRIME.append(i)

for p in PRIME:
 for q in PRIME:
  if p+(2*q)>=MAX:
   break
  B[p+(2*q)]+=1

for _ in range(int(input())):
 n=int(input())
 print(B[n])

  
  


from sys import stdout
from bisect import *
def fun(n,f):
 ct=1
 while n%f==0:
  ct+=1
  n//=f
 return ct
N=1000009
l=[0]*N
a=[0]*N
b=[1]*N
for i in range(N):
 l[i]=i
for i in range(2,N):
 if l[i]>0:
  a[i]+=1
  b[i]+=1
  j=i+i
  while j<N:
   l[j]=0
   a[j]+=1
   b[j]*=fun(j,i)
   j+=i
arr=[]
for i in range(2,10000):
 if l[i]>0:
  arr.append(i)
lis=[0]*(10001)
for i in arr:
 for j in arr:
  if i+2*j<=10000:
   lis[i+2*j]+=1
for i in range(int(input())):
 print(lis[int(input())])

import math
maxn = 10**4 + 1
x = [a for a in range(2,maxn)]
for y in x:
 for j in range(2,math.ceil(maxn/y)):
  if y*j in x:
   x.remove(y*j)
val = [0]*(3*(10**4))
for i in range(len(x)):
 for j in range(len(x)):
  val[(x[i]+2*x[j])]+=1
t=int(input())
for i in range(t):
 n=int(input())
 print(val[n])

def sieve(n):
 #Create list of numbers from 0 to n
 #True denotes prime, false not prime 
 l=[True for i in range(n+1)]
 #Start with 2
 p=2
 while(p*p<n):
  #and cross off all it's multiples 
  if l[p]: 
   for i in range(p*p, n+1, p): 
    l[i] = False
  #increment p to next value 
  p+=1
 #adding all prime numbers to a list and returning it 
 primes=[]
 for i in range(2,n):
  if l[i]:
   primes.append(i)
 return primes

sums=[0]*(10001)
p=sieve(10001)

#calculating all possible sums as per question and storing the count of each
for i in p:
 for j in p:
  if i+(2*j) <= 10000:
   sums[i+(2*j)]+=1

#input number of test cases
t=int(input())
while t:
 n=int(input())
 #input number and check if it is in the pre-built list
 print(sums[n])
 t-=1

import math
MAX = 10**4
#sieve of eratosthenes
#for finding all primes till 10000
primes = [1 for i in range(MAX)]
for i in range(2,int(math.sqrt(MAX))+1):
 if primes[i]==1:
  for j in range(i*i,MAX,i):
   primes[j] = 0

#calculating number of pairs for all possible inputs
n_pairs = [0 for i in range(MAX + 1)]
PRIMES = [x for x in range(2,len(primes)) if primes[x]==1]
for i in PRIMES:
 for j in PRIMES:
  if i + 2*j <= MAX:
   n_pairs[i + 2*j] += 1
  
for _ in range(int(input())):
 print(n_pairs[int(input())])

def Prob1(n) :
 pr=[True for i in range(n+1)]
 p=2
 while(p*p <n) :
  if (pr[p] == True): 
   for i in range(p * 2, n+1, p): 
    pr[i] = False
  p += 1
 prime=[]
 for i in range(2,n) :
  if pr[i] :
   prime.append(i)
 return prime
prr=Prob1(10001)
pair=[0]*(10001)
for i in prr :
 for j in prr :
  if(i+(2*j))<=10000 :
   pair[i+(2*j)]+=1
T=int(input())
for _ in range (T) :
 N=int(input())
 print(pair[N])


def sieve(n):
 '''
    Sieve of eratosthenes
    Returns primesd: dictionary of primes upto n
      primesl: list of primes upto n
    '''
 l = [True]*(n+1)
 l[0] = False
 l[1] = False
 for i in range(2, n+1):
  j = i*i
  while j < n+1:
   l[j]=False
   j+=i
 primesd={}
 primesl = []
 for i in range(2, n+1):
  if l[i]:
   primesd[i]=True
   primesl.append(i)
 return primesd, primesl

primesd, primesl = sieve(10000)
pc = [0]*10001 # pc:- pair count

# pre-computing the counts for fast retreival
for e in primesl:
 for f in primesl:
  temp = e+2*f
  if temp > 10000:
   break
  pc[temp]+=1

t =int(input())

for __ in range(t):
 n = int(input())
 print(pc[n])


# calculate primes
def calcPrimes(tot):
 fin = []
 primes = [1]*(tot+1)
 start = 2

 while start < tot+1:
  fin.append(start)
  
  # mark all factors of the given number      
  for i in range(2*start,tot+1,start):
   primes[i] = 0

  start +=1
  # check next unmarked number
  while start < len(primes) and primes[start] == 0:
   start += 1
 return fin

primes = calcPrimes((10**4)+5)
count = [0]*((10**4)+5)

# mark possibility for each pair
for i in primes:
 for j in primes:
  if (i+(2*j)) < len(count):
   count[(i+(2*j))] += 1

n = int(input())
for _ in range(n):
 print(count[int(input())])


def calcPrimes(tot):
 fin = []
 primes = [1]*(tot+1)
 start = 2

 while start < tot+1:
  fin.append(start)
  
  for i in range(2*start,tot+1,start):
   primes[i] = 0

  start +=1
  while start < len(primes) and primes[start] == 0:
   start += 1

 return fin

def solve(tot,primes,primeSet):
 pairs = 0
 for i in primes:
  if (tot-i)%2==0 and (tot-i)//2 in primeSet:
   pairs += 1
  if (tot - (2*i)) in primeSet:
   pairs += 1
 print(pairs//2)


primes = calcPrimes((10**4)+5)
count = [0]*((10**4)+5)
for i in primes:
 for j in primes:
  if (i+(2*j)) < len(count):
   count[(i+(2*j))] += 1

n = int(input())
for _ in range(n):
 print(count[int(input())])


def SieveOfEratosthenes(n):
 prime = [True for i in range(n+1)]
 p = 2
 while (p * p <= n):
  if (prime[p] == True):
   for i in range(p * p, n+1, p):
    prime[i] = False
  p += 1
 pr = []
 for i in range(2,10**4 + 1):
  if prime[i]:
   pr.append(i)
  pcount[i] = 0
 for i in pr:
  for j in pr:
   try:
    pcount[i + 2 * j] += 1
   except:
    continue

pcount = [0]*10001
SieveOfEratosthenes(10**4 + 1)
for _ in range(int(input())):
 print(pcount[int(input())])

N = 10005

marker = [0]*N
PRIMES = []
levy = [0]*N

# PRECAL PRIMES
marker[0] = marker[1] = 1 # marked non primes
for i in range(2, int(N**0.5)):
 for j in range(i*i,N,i):
  marker[j] = 1

for i in range(N):
 if not marker[i]:
  PRIMES.append(i)

# PRECAL LEVY
n_primes = len(PRIMES)

for i in range(n_primes):
 a = PRIMES[i]
 for j in range(n_primes):
  b = PRIMES[j]
  if a + 2*b < N:
   levy[a + 2*b] += 1

# MAIN

t = int(input())

for _ in range(t):
 n = int(input())
 print(levy[n])


from collections import defaultdict
n=10002
prime=[1]*n
prime[0]=0
prime[1]=0
primelist=[]
pairs=defaultdict(list)
for i in range(2,n):
 if prime[i]==1:
  primelist.append(i)
  for j in range(i*i,n,i):
   prime[j]=0
d=defaultdict(int)
for p in primelist:
  for q in primelist:
   d[p+2*q]+=1
   pairs[p+2*q].append((p,q))
t=int(input())
while t:
 t-=1
 num=int(input())
 print(d[num])
 #print(pairs[num])