文章标题

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

Hint

解题报告

先得对107$10^7$ 内的素数打表只有664580个，如此数据量级就减小了100倍

判断素数a+b=n，只要取素数a，在判断 n-a 是否为素数即可复杂度o(φ(n))