Problem C: Factor, Factor (2011-ish)

You recently became obsessed with prime numbers; that is, any positive integer that is only evenly divisible by one and itself (e.g., 2, 3, 5, 7, 11, ...). You have found that any (positive) integer can be factored into a product of primes. For example, 175 = 5²×7.

But factoring numbers by hand is painful. So, you decide to write a program to factor numbers.

input

The input will be a list of positive integers, one per line, each between 1 and 1,000,000, inclusive. (There are exactly 78,498 primes below one million!) The last line of the input will be “0” which indicates the end of the input (and which you do not process).

Sample Input

5
1
24
175
135200
1000000
0

There will be at most 100 lines of input.

Output

Your output should consist of one line per input line (except for the terminating “0”), reporting the factoring of the corresponding number. The factoring should list the prime factors in increasing order, using an exponent to indicate the number of times each factor divides into it. In the case the exponent is 1, the exponent is not to be printed. Use “^” to indicate the exponent, and “*” between the terms.

Sample Output

5

2^3*3
5^2*7
2^5*5^2*13^2
2^6*5^6