旅行者想到了一个公式，这个公式是这样的：
给定某个正整数$N$，求其质因子分解结果，及给出其因式分解表达式：

$$N=p^{k_1}_{1}\times p^{k_{2}}_{2}\times ... \times p^{k_m}_{m}$$

神里凌华说：“如果你算出来了我给你的挑战，那么你将获得奖励”

第一行：神里凌华的T个测试用例
第2~T+1行：一个整数$N$

按照给定格式输出$N$，及N=p1^k1*p2^k2*...*pm^km，其中pi为质因子，并要求从小到大。指数ki为pi的个数；当ki为1即因子pi只有一个时不输出ki
当$N=1$时输出1=1。

$$1\le N \le 9,223,372,036,854,775,807$$

提示：可以使用long long

$$long long最大存贮范围：9,223,372,036,854,775,807$$

时间限制：$400ms$，空间限制$128MB$

测试点数据保证：

测试点编号	测试点数据范围
1~2	$1$ ~ $114514$
3~5	$1$~ $2,147,483,647$
5~7	$1000$~$10^{12}$
8~11	$114514 ~ 9,223,372,036,854,775,800$
12~13	$1$ ~ $9,223,372,036,854,775,807$

$$\tiny \text{读入文件名：Genshin.in}{写入文件名：Genshin.out}$$

作者AC出品必须优秀！ 来 关注一下 谢谢（会回关）