Input

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào một số nguyên dương \(n\) (\(2 \le n\))

Output

• Với mỗi truy vấn, hãy in ra số n sau khi đã phân tích thành thừa số nguyên tố.
• In ra kết quả dưới dạng luỹ thừa. VD: 8 = 2^3, 12 = 2^2*3, ...

Example

5
6
7
12
15
18

2*3
7
2^2*3
3*5
2*3^2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(t \le 10\), \(n \le 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): \(t \le 10\), \(n \le 10^{12}\).
• Subtask \(3\) (\(30\%\) số điểm): \(t \le 10^6\), \(n \le 2\cdot 10^7\).