Dato je n brojeva. Potrebno je faktorisati svaki broj, tj. napisati ga kao proizvod prostih činioca. Svaki broj faktorisati u formatu p₁^a₁ \ p₂^a₂ * ... * p_k^a_k , gde su p₁ ≤ p₂ ≤ ... ≤ p_k svi prosti činioci datog broja (u rastućem redosledu), a a₁, a₂, ..., a_k - njihovi odgovarajući izložioci. Izmedju brojeva i simbola '\' i '^' ne sme biti razmaka.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom redu standradnog ulaza nalazi se prirodan broj n ≤ 200.000. U sledećih n redova se nalazi po jedan ceo broj b_i koga treba faktorisati (2 ≤ b_i ≤ 200.000).

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) Na standardni izlaz za svaki broj ispisati u posebnom redu njegovu faktorizaciju u gore opisanom formatu, u redosledu datim na ulazu.

Ograničenja.

U 40% test primera n ≤ 1.000

Primer 1.

3
10
23
180 

2^15^1
23^1
2^23^2*5^1