Any natural number can be expressed as the sum of , or odd primes. If itself is a prime, only one number is required.
However, because there are so many solutions for large composite , it is your task to find the solution where are prime, and where is as large as possible, or, if cannot be expressed as the sum of two primes, find the solution where are prime and where is as large as possible, followed by where is as large as possible.
is larger than and so, the required solution is .
In this case, is larger than , and so the required solution is .
The input contains numbers on separate lines. These numbers are less than and larger than . Write a program that will find the sum of primes for each of these numbers as described, and display the result as is shown in the sample below.
49 152029 90118 4565973 705510
49 = 13 + 17 + 19 152029 = 152029 90118 = 44987 + 45131 4565973 = 1521991 + 1521991 + 1521991 705510 = 352753 + 352757