In 1742, Christian Goldbach, an amateur German mathematician, conjectured that every even number greater than two is the sum of two prime numbers. His conjecture is, as yet, unproven, although it is known to hold for all numbers up to some number in the millions.
For example, 8 is the sum of the prime numbers 3 and 5. Some even numbers are such that there are several pairs of primes that sum to them. For example, each of the following pairs of primes has sum 36: (5,31), (7,29), (13,23), (17,19).
Develop a program that, given an even integer m greater than two, determines the number of distinct pairs of primes whose sum is m. (For example, for 36 this would be four.)
The input will be sequence of even numbers in the range 4..100,000 (four to one hundred thousand), one per line. For each such number, the program should produce a line of output containing the input value followed by the number of distinct pairs of primes that sum to it.
Sample Input
4 36
Sample Output
4 1 36 4