题目描述

给定$T$个正整数,要求对于每个数,都输出其质因数分解

输入格式

第1行一个正整数$T$

第2行$T$个正整数$a_i$，表示每个数

输出格式

$T$行，第$i$行对应第$i$个数的质因数分解。

输出格式：$P_1$^${c_1} * {P_2}$^${c_2}…*P_m$^${c_m}$

其中，$P_1,P_2, …,P_m$为递增的互不相同的质素，$c_i$为1时省略。

样例

2
24 25

2^3*3
5^2

数据规模

• $a_i<3*10^6$
• $T$<20

提示

维护1~$T$每个数最小约数，可以发现它必然为质素