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:</p>

• 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