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*2*3*4*5*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 24*32*51. 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 ≤ n puterea la care acesta apare în descompunerea în factori primi a lui n!.

Cerința

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, 60000].
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*2*2*2*2*2*2*3*3*5*7
15! = 2*2*2*2*2*2*2*2*2*2*2*3*3*3*3*3*3*5*5*5*7*7*11*13
10! = 2*2*2*2*2*2*2*2*3*3*3*3*5*5*7