碑文密钥的拆解

题目描述

古堡大厅中央立着一块石碑，碑面上刻着一串正整数，每个数都代表一段锁链的“密钥”。管理员说：想要制作复制钥匙，必须把每个密钥拆解成若干“基础齿纹”，并记录每种齿纹出现的次数。

现在给出这串密钥，请你为每个密钥输出其拆解结果，以便铁匠按照规格铸造。

输入格式

第一行一个整数 q，表示密钥的数量。 接下来 q 行，每行一个整数 x，表示一个密钥。

输出格式

输出共 q 行。对每个密钥 x，将其拆解成若干“基础齿纹”的乘积，并按“齿纹 基数^出现次数”的形式自小到大输出，各部分之间用一个空格分隔。

例如 360 的拆解应输出为 2^3 3^2 5^1。

输入输出样例 #1

输入 #1

5
2
3
4
360
999983

输出 #1

2^1
3^1
2^2
2^3 3^2 5^1
999983^1

说明/提示

• 可将“基础齿纹”理解为大于 1 的自然数的“不可约构件”，即只可被 1 和自身整除的数。
• 对于 100% 的数据，1 <= q <= 1e5，且每个 x 满足 2 <= x <= 1e7。建议先准备必要的辅助信息，再对每个密钥快速拆解。