Un numar natural a se numeste putere daca exista numerele naturale b si c, c>1 astfel incat a=b^c.

Fie N un numar natural. Numarul N poate fi scris in mai multe moduri ca suma de puteri. O posibilitate ar fi, de exemplu, N=1+1+...+1 (N termeni egali cu 1).

Date de intrare

Fisierul de intrare puteri.in contine pe prima linie numarul natural N.

Date de iesire

Fisierul de iesire puteri.out contine doua linii. Pe prima linie se afla un numar natural nenul nr, reprezentand numarul de termeni din suma (minim). Pe cea de a doua linie se afla nr puteri, separate prin cate un spatiu, scrise in ordine crescatoare. Daca exista mai multe solutii, va fi afisata cea mai mica in ordine lexicografica.

• 1 <= N <= 30000
• Secventa x₁ x₂ ... x_k este mai mica in ordine lexicografica decat secventa y₁ y₂ ... y_h daca exista o pozitie i>0 astfel incat x₁=y₁, x₂=y₂, ..., x_i-1=y_i-1 si (x_i<y_i sau i=k+1).

Timp maxim de executie/test: 0.1 secunde.