시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 64 MB31282589.286%

문제

One of the oldest and best-known unsolved problems in Mathematics is Goldbach's conjecture. It states that every even integer greater than 2 can be expressed as the sum of two primes. The expression of a given even number as a sum of two primes is called a Goldbach partition of that number. The following are examples of Goldbach partitions for some even numbers:

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

Your task is to write a program to check the number of Goldbach partitions for a given even number.

입력

An even integer n (4 <= n <= 10000000) will be given in each input line. The end of input is indicated by a number 0.

출력

For each line of input, print an integer in one line showing the number of Golbach partitions.

예제 입력 1

4
10
100
0

예제 출력 1

1
2
6