Goldbach Partitions

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.

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.

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