Goldbach Partitions

Time limit3sMemory limit64 MB

Summary

Count the pairs of primes that sum to each given even number up to ten million.

Level: Medium4 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

Goldbach's conjecture is one of the oldest unsolved problems in mathematics. It claims that every even integer greater than $2$ can be written as the sum of two primes. An even number written as such a sum is called a Goldbach partition of that number. Two sums that use the same pair of primes in a different order are the same partition, so $10 = 3 + 7$ and $10 = 7 + 3$ count once.

Here are a few even numbers with all of their Goldbach partitions.

$4 = 2 + 2$
$10 = 3 + 7 = 5 + 5$
$100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53$

So $4$ has one partition, $10$ has two, and $100$ has six. Count the Goldbach partitions of every even number you are given.

Input

Each line of the input holds one even integer $n$ ( $4 \le n \le 10^7$ ). A line holding $0$ marks the end of the input and is not a query.

Output

For each even number in the input, print the number of its Goldbach partitions on its own line, in input order.

Examples2

Example 1
Input
```
4
10
100
0
```
Expected output
```
1
2
6
```
Example 2
Input
```
6
8
12
14
16
18
20
0
```
Expected output
```
1
1
1
2
2
2
2
```