Gorszy Goldbach

Limit pamięci: 32 MB

W roku 1742 C. Goldbach w liście do L. Eulera napisał, że jego zdaniem każda liczba całkowita jest sumą trzech liczb pierwszych (liczba pierwsza to liczba naturalna , która ma tylko dwa dzielniki naturalne: 1 oraz ). Euler odpisał, że jest to równoważne temu, że każda liczba parzysta jest sumą dwóch liczb pierwszych. To jednak nie przybliżyło ich do rozwiązania podstawowego problemu: czy tak jest naprawdę. Dziś wiemy, że jest tak dla liczb aż do (wiemy też dużo więcej, ale cała hipoteza jest nadal problemem otwartym). Nie będziemy tego sprawdzać, postawimy sobie mniej ambitne zadanie. Okazuje się, że każda liczba naturalna jest sumą różnych nieparzystych liczb pierwszych.

Twoje zadanie polega na napisaniu programu, który:

• wczyta ze standardowego wejścia liczby całkowite,
• znajdzie ich rozkłady na sumy różnych nieparzystych liczb pierwszych,
• wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisano jedną dodatnią liczbę całkowitą , . W każdym z kolejnych wierszy znajduje się jedna liczba całkowita z przedziału .

Wyjście

Rozkład liczby musi być zapisany w dwóch wierszach standardowego wyjścia. W pierwszym wierszu należy zapisać jedną liczbę całkowitą , będącą liczbą składników rozkładu. W drugim wierszu należy zapisać, w rosnącej kolejności, różnych nieparzystych liczb pierwszych, których suma jest równa , pooddzielanych pojedynczymi odstępami. Rozkłady powinny występować w kolejności zgodnej z kolejnością liczb na wejściu.

Przykład

Dla danych wejściowych:

2
59
15

poprawną odpowiedzią jest:

5
5 7 11 17 19
3
3 5 7

Autorzy zadania: Wojciech Guzicki, Jarosław Wróblewski.