Faktorizácia

Každé celé číslo má jednoznačne určený rozklad na prvočísla, až na poradie. Nájdenie rozkladu čísla sa nazýva faktorizácia. Dostanete niekoľko čísel ­— faktorizujte ich.

Vstup

V prvom riadku je celé číslo $1 \leq t \leq 20$ - počet čísel na faktorovanie. V ďalších $t$ riadkoch je jedno celé číslo $2 \leq n \leq 10^{12}$.

Výstup

Pre každé číslo vypíšte jeho faktorizáciu, ako je uvedené v príklade. Prvočísla vypisujte od najmenšieho po najväčšie.

Prí­klad

2
47
868

47 = 47
868 = 2 x 2 x 7 x 31