Woburn Challenge 1999

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 ~n~ ~(4 \le n \le 16\,000)~ may be written as a sum of ~2~ primes. (Note that Goldbach believed that ~1~ was prime).

Input Specification

A series of integers in the range ~4 \le n \le 16\,000~, terminated by the number -1.

Output Specification

Output ALL distinct pairs of primes ~(a, b)~ (where ~a \le b~) such that ~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

4
8
-1

Sample Output

1 3
2 2

1 7
3 5