Goldbach's Conjecture

Interview

Time limit0.5sMemory limit256 MB

Summary

For each even n up to one million, find the split into two odd primes with the largest difference, printing n = a + b.

Level: Medium4 of 10
Topics: Number theory, Math, Brute force, Implementation
Solved: No attempts yet

Problem

In 1742, the German amateur mathematician Christian Goldbach sent a letter to Leonhard Euler proposing the following conjecture.

Every even number greater than 4 can be written as the sum of two odd prime numbers.

For example, $8 = 3 + 5$ , and both 3 and 5 are odd primes. Likewise, $20 = 3 + 17 = 7 + 13$ and $42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23$ .

This conjecture remains unproven to this day.

Write a program that verifies this conjecture for every even number up to one million.

Input

The input consists of one or more test cases. The number of test cases does not exceed 100,000.

Each test case consists of a single even integer $n$ ( $6 \le n \le 1000000$ ).

The last line of the input contains a single $0$ , which marks the end of the input.

Output

For each test case, print the result in the form $n = a + b$ , where $a$ and $b$ are odd primes. The numbers and the operator are separated by a single space. If there are several ways to express $n$ as a sum of two odd primes, print the one for which $b - a$ is the largest. If $n$ cannot be written as the sum of two odd primes, print Goldbach's conjecture is wrong.

Examples1

Example 1

Input

Expected output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37