F001B. Goldbach's Conjecture P72452

In 1742, the mathematicians Leonard Euler and Christian Goldbach exchanged letters where they claimed that an even number greater or equal than four can be written as a sum of two odd numbers. This property, called Goldbach’s conjecture, has still neither been proved nor disproved, despite of it happened 260 years ago. However, using computers, it has been proved that Goldbach’s conjecture is true for numbers less than $10^{14}$.

Implement a procedure

    void goldbach(int n, const vector<int>& v, int j);

that prints each pair of odd numbers $p$ and $q$ with $p \le q$ such that $p + q =$ |n|. As preconditions, we know that |n| is an even number and that $4 \le$ |n| $\le 100000$.

In order to help you solving this problem, the header includes two additional parameters: Vector |v| contains, in order, the first 9592 prime numbers less than 100000. Its content is:

Integer |j| indicates the position in |v| of the maximal odd number less than |n|. For instance, if |n| $= 4$, |j| $= 1$; if |n| $= 6$, |j| $= 2$; if |n| $= 8$ or |n| $= 10$, |j| $= 3$; …; if |n| is between 99972 and 99988, |j| $= 9589$; if |n| $= 99990$, |j| $= 9590$; and if |n| is between 99992 and 100000, |j| $= 9591$.

You do not need to understand the main program, which is already implemented; do not modify it. It calculates some tables with information to call your |goldbach()| with the suitable parameters for each read number.

Input

The input is a sequence of natural even numbers between 4 and 100000 (both included).

Output

For each |n|, you must write the number |n| followed by ‘|=|’. Afterwards, with a ‘|+|’ sign between and separated by commas, you must write each different pair of prime numbers $p$ and $q$ with $p \le q$ whose sum is |n|. You must write the pair in increasing order with regard to $p$. Follow the format of the instance.

Observation

The program that checks if $p + q =$ |n| for each pair of prime numbers $p$ and $q$ with $p \le q <$ |n|, will be rejected for being too much slow.