Problem Description

As everyone knows, Goldbach's conjecture says that any even number greater than $2$ can be written as the sum of two prime numbers. For example:

• $4=2+2$
• $6=3+3$
• $8=3+5$
• $10=3+7=5+5$

You surely want to know: for an even number $n$ greater than $2$, how many ways are there to write it as the sum of two primes? For example, $4$, $6$, and $8$ each have only one way, while $10$ has two ways. Please write a program to compute the answer.

In this problem, we consider two representations different if and only if the sets of primes used in the two representations are different. That is, $10=3+7$ and $10=7+3$ are the same representation and must not be counted twice.

Input Format

One line containing an even integer $n$ greater than $2$.

Output Format

One line containing an integer, representing the number of ways to write $n$ as the sum of two primes.

4

1

10

2

Hint

For $40\%$ of the test points, $4 \le n \le 100$ is guaranteed.

For all test points, $4 \le n \le 10^6$ is guaranteed.

Translated by ChatGPT 5