FACT2 - Integer Factorization (29 digits)

**题目描述** 给出一个数n，分解质因数。 **输入格式** 一个正整数n（会有若干行(大约10行)，并以0结束）（n<10^29） **输出格式** 每输入一行，会以x^y形式输出(x为质数，y为x的乘方，之间用空格分开)

This is a problem to test the robustness of your Integer Factorization algorithm. Given some integers, you need to factor them into product of prime numbers. The largest integer given in the input file has 29 digits. You may need to use a general factorization algorithm since no special numbers (e.g. Fermat numbers) are considered when designing the input data.

There are several numbers given, each one in a line. The input ends with a number 0. The number of test cases is about 10.

For each number, print in a line the factorization of it. See examples below for the output format.

3111989
13091989
2432902008176640000
77145199750673
0

317^1 9817^1
17^2 89^1 509^1
2^18 3^8 5^4 7^2 11^1 13^1 17^1 19^1
328439^1 234884407^1