Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Every even integer, greater than 2, can be expressed as the sum of two primes [1].

Now your task is to check whether this conjecture holds for integers up to 107.

Input

Input starts with an integer T (≤ 300), denoting the number of test cases.

Each case starts with a line containing an integer n (4 ≤ n ≤ 107, n is even).

Output

For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where

1)      Both a and b are prime

2)      a + b = n

3)      a ≤ b

Sample Input

2

6

4

Sample Output

Case 1: 1

Case 2: 1

 题意：每一个大于2的偶数可以表示为两个素数的和，给出一个数，看看它存在多少种情况。这两个素数必须满足 a + b = n和

a ≤ b。

题解：素数打表。

​
//埃氏筛选（素数打表）
//哥德巴赫的猜想
//先进行一个素数打表，把数据范围内所有素数存在一个数组内，
//此时已经是从小到大排好的了，然后从数组中的第一个1到最后一个遍历，
//如果n减去该元素的值还是一个素数的话num++，如果该元素大于等于n/2+1，
//结束遍历。输出num的值即可。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
bool book[10000100];
int su[1000000];
int main()
{
    int t;
    memset(book,0,sizeof(book));
    memset(su,0,sizeof(su));
    book[0]=book[1]=1;
    int l=0;
    for(int i=2; i<10000000; i++)//**********
    {
        if(book[i]==0)
        {
            su[l++]=i;
            for(int j=i*2; j<10000000; j+=i)
                book[j]=1;
        }
    }
    scanf("%d",&t);
    int o=1;
    while(t--)
    {
        int n,num=0;
        scanf("%d",&n);
        for(int i=0; i<l; i++)
        {
            if(su[i]>=n/2+1)//满足a<=b的情况。
                break;
            if(book[su[i]]==0)
            {
                if(book[n-su[i]]==0)
                {
                    num++;
                }
            }
        }
        printf("Case %d: %d\n",o++,num);
    }
    return 0;
}
/*
     n==10
su[0]=2,su[1]=3,su[2]=5,su[3]=7.....
可执行的情况： 3+7,5+5
不存在：7+3    su[i]==7时break：(su[i]>=n/2+1)
*/

​