Goldbach's Conjecture

Interview

Time limit1sMemory limit128 MB

Summary

For each even n below 2^15, count the unordered pairs of primes that sum to n, stopping at a terminating 0.

Level: Easy3 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

It is conjectured that every even number $n$ that is at least 4 can be written as the sum of two prime numbers $p_1$ and $p_2$ :

$n = p_1 + p_2$

This conjecture has been neither proven nor disproven. Even so, for any given even number you can search directly for such prime pairs and count them.

Several even numbers are given as input. For each one, write a program that outputs the number of prime pairs satisfying the condition above. Count only essentially different pairs: $(p_1, p_2)$ and $(p_2, p_1)$ are considered the same pair and must not be counted twice.

Input

Each line contains a single integer. Every integer is even and satisfies $4 \le n < 2^{15}$ . The end of the input is indicated by the number $0$ .

Output

For each even number, output the number of prime pairs satisfying the condition, one per line. No other characters should appear in the output.

Examples4

Example 1
Input
```
6
10
12
0
```
Expected output
```
1
2
1
```
Example 2
Input
```
8
0
```
Expected output
```
1
```
Example 3
Input
```
100
0
```
Expected output
```
6
```
Example 4
Input
```
1000
0
```
Expected output
```
28
```