CLSUMG_setter.java

import java.io.*;
import java.util.*;
class goldbach
{
    public static void main(String[] args)
    {
           Scanner in = new Scanner(System.in);
           StringBuilder sb=new StringBuilder();
           int t=in.nextInt();
           int i,j,factor;
           int n=1100001,k=0;
           boolean[] isprime=new boolean[n];
           for(i=2;i<n;i++)
               isprime[i]=true;
           for(factor=2;factor*factor<n;factor++)
           {
                if(isprime[factor])
                {
                    for(j=factor;factor*j<n;j++)
                        isprime[factor*j]=false;
                }
           }
           long arr1[]=new long[1000001];
           for(i=0;i<=1000000;i++)
           {
               if(isprime[i])
               arr1[i]=1;
           }
           long ans1[]=FastFourierTransform.multiply(arr1,arr1);
           int size=ans1.length;
           for(i=0;i<size;i++)
           {
               if(i%2==0 && isprime[i/2])
                    ans1[i]=(ans1[i]+1)/2;
               else
                    ans1[i]=ans1[i]/2;
           }
           while(t-->0)
           {
                long a=in.nextInt();
                long freq[]=new long[16139];
                for(i=0;i<a;i++)
                    freq[(int)ans1[i]]++;
                int x=(int)ans1[(int)a];
                long count=0;
                for(i=0;i<=x/2;i++)
                {
                    if(i==(x-i))
                        count+=freq[i]*(freq[i]+1)/2;
                    else
                        count+=freq[i]*freq[x-i];
                }
                sb.append(count).append("\n");
           }
           System.out.println(sb);
            
    }
}
class FastFourierTransform {
    public static void fft(double[] a, double[] b, boolean invert) {
        int count = a.length;
        for (int i = 1, j = 0; i < count; i++) {
            int bit = count >> 1;
            for (; j >= bit; bit >>= 1)
                j -= bit;
            j += bit;
            if (i < j) {
                double temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                temp = b[i];
                b[i] = b[j];
                b[j] = temp;
            }
        }
        for (int len = 2; len <= count; len <<= 1) {
            int halfLen = len >> 1;
            double angle = 2 * Math.PI / len;
            if (invert)
                angle = -angle;
            double wLenA = Math.cos(angle);
            double wLenB = Math.sin(angle);
            for (int i = 0; i < count; i += len) {
                double wA = 1;
                double wB = 0;
                for (int j = 0; j < halfLen; j++) {
                    double uA = a[i + j];
                    double uB = b[i + j];
                    double vA = a[i + j + halfLen] * wA - b[i + j + halfLen] * wB;
                    double vB = a[i + j + halfLen] * wB + b[i + j + halfLen] * wA;
                    a[i + j] = uA + vA;
                    b[i + j] = uB + vB;
                    a[i + j + halfLen] = uA - vA;
                    b[i + j + halfLen] = uB - vB;
                    double nextWA = wA * wLenA - wB * wLenB;
                    wB = wA * wLenB + wB * wLenA;
                    wA = nextWA;
                }
            }
        }
        if (invert) {
            for (int i = 0; i < count; i++) {
                a[i] /= count;
                b[i] /= count;
            }
        }
    }
 
    public static long[] multiply(long[] a, long[] b) {
        int resultSize = Integer.highestOneBit(Math.max(a.length, b.length) - 1) << 2;
        resultSize = Math.max(resultSize, 1);
        double[] aReal = new double[resultSize];
        double[] aImaginary = new double[resultSize];
        double[] bReal = new double[resultSize];
        double[] bImaginary = new double[resultSize];
        for (int i = 0; i < a.length; i++)
            aReal[i] = a[i];
        for (int i = 0; i < b.length; i++)
            bReal[i] = b[i];
        fft(aReal, aImaginary, false);
        fft(bReal, bImaginary, false);
        for (int i = 0; i < resultSize; i++) {
            double real = aReal[i] * bReal[i] - aImaginary[i] * bImaginary[i];
            aImaginary[i] = aImaginary[i] * bReal[i] + bImaginary[i] * aReal[i];
            aReal[i] = real;
        }
        fft(aReal, aImaginary, true);
        long[] result = new long[resultSize];
        for (int i = 0; i < resultSize; i++)
            result[i] = Math.round(aReal[i]);
        return result;
    }
}