factori

Gigel a aflat la matematică definiția factorialului unui număr natural nenul $n$. Acesta este produsul tuturor numerelor naturale începând cu $1$ și terminând cu numărul respectiv și se notează cu $n!$. Astfel, factorialul numărului natural $6$ este $6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6$ și este egal cu $720$. Factorialele numerelor naturale cresc însă extrem de repede. De exemplu, $7! = 5040$ în timp ce $10! = 3628800$.

Fiind un bun matematician, Gigel a imaginat o altă metodă de a indica factorialul unui număr. Astfel, el știe că un număr natural nenul se poate descompune în factori primi. De exemplu $720$ poate fi scris ca $2^4 \cdot 3^2 \cdot 5^1$. Gigel codifică descompunerea în factori primi astfel: $4 \ 2 \ 1$ însemnând faptul că în descompunerea lui $720$ în factori primi apare factorul $2$ de $4$ ori, factorul $3$ apare de două ori și factorul $5$ apare o dată. Cu alte cuvinte, Gigel indică pentru fiecare număr prim $\leq n$ puterea la care acesta apare în descompunerea în factori primi a lui $n!$.

Cerință

Scrieți un program care să citească o secvență de numere naturale nenule și care să afișeze în modul descris în enunț factorialele numerelor citite.

Date de intrare

Fișierul de intrare factori.in conține mai multe numere naturale nenule, câte un număr pe linie. Ultima linie a fișierului de intrare conține valoarea $0$ indicând faptul că setul de numere s-a terminat.

Date de ieșire

Fișierul de ieșire factori.out va conține câte o linie pentru fiecare număr nenul din fișierul de intrare. Pe linia $i$ din fișierul de ieșire va fi descrisă descompunerea în factori primi a factorialului numărului de pe linia $i$ din fișierul de intrare, în modul descris în enunț. Numerele scrise pe aceeași linie vor fi separate prin câte un spațiu.

Restricții și precizări

• Numerele naturale din fișierul de intrare (exceptând ultimul) sunt din intervalul $[2, 60 \ 000]$.
• Fișierul de intrare conține maxim $10$ numere naturale nenule.

Exemplu

factori.in

2
8
15
10
0

factori.out

1
7 2 1 1
11 6 3 2 1 1
8 4 2 1

Explicație

$2! =2$
$8!=2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 \cdot 7$
$15!= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdot 11 \cdot 13$
$10!=2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdot 7$