For this prelude, you are to find all the prime factors of a number.

Input consists of a sequence of non-negative integers, one per line, each less than 2^31. The last entry is a 0, which should not be processed.

For each non-zero input value, n, determine find the prime factors. Print all factors on a single line as a sequence of terms of the form p^m, indicating that prime p appears m times in n.

Print the primes in numerical order, lowest to highest. Do not print any primes whose exponent is 0.

7
10
0

7^1
2^1 5^1