题目描述

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

输入格式：

第1行一个正整数T；第2行T个正整数，表示每个数。

输出格式：

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

输出形式：

$p_1^{c_1}*p_2^{c_2}...*p_m^{c_m}$ 其中，$p1,p2,...,pm$ 为递增的互不相同的质数，$c_i$为1时省略。

提示：维护1~T每个数最小的约数，可以发现它必然为质数。

样例

2
24 25

2^3*3
5^2

Limitation

1s, 1024KiB for each test case.