시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 64 MB 1 1 1 100.000%

문제

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.

예제 입력

4
10
100
0

예제 출력

1
2
6

힌트