WOBURN CHALLENGE 1999

INPUT FILE: gold.in
OUTPUT FILE: gold.out

Think back to the 1960s. Remember Goldfinger? Well, it appears he was cryofrozen and traveled back in time to the mid 1700s, where he was reanimated as his alter ego Goldbach, the famous mathematician. Coincidentally, MI6 cryofroze James Bond and sent him back to a similar time to thwart the latest evil plan of the evil genius. Goldbach plans to distract all of the world's greatest intelligentsia by having them work with the dreaded ... unproven conjecture. He knows that an unproven conjecture (especially one as fiendish as his Binary Goldbach Conjecture) is sheer craziness and will drive all of the world's mathematicians to insanity, thus resulting in an effective end to mathematical development, thus plunging the world into the Dark Ages once more. But where mathematicians fail, scientists (and doctors) reign supreme and James Bond will attempt to prove the theorem by a tried-and-true scientific method: proof by example.

Goldbach's Binary Conjecture: Every even number 4 <= n <= 16000 may be written as a sum of 2 primes. (Note that Goldbach believed that 1 was prime).

INPUT
A series of integers in the range 4<=n<=16000, terminated by the number -1.

OUTPUT
Output ALL distinct pairs of primes a,b (a <= b) such than n = a + b; leave a blank line after each output set. The output should come sorted, in increasing order, by the first number (a). There may be as many as 200 numbers in the input file. An input of '-1' denotes the end of data. (Recall that a prime number is one that has no divisors other than one and itself. Also, count "1" as a prime.)

Sample Input File

4
8
-1

Output for Sample Input

1 3
2 2

1 7
3 5