## FACT0 - Integer Factorization (15 digits)

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 15 digits. FACT1 is a harder version of this problem (the numbers are larger).

You may need to use a general factorization algorithm since no special numbers (e.g. Fermat numbers) are considered when designing the input data.

### Input

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.

### Output

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

### Example

Input:
3111989
13091989
77145199750673
0

Output:
317^1 9817^1
17^2 89^1 509^1
328439^1 234884407^1

hide comments
 karan: 2015-03-30 17:05:13 finally ac :') Takanori MAEHARA: 2015-02-17 23:35:51 What should be the output for 1? (Francky) => No case like that. Last edit: 2015-02-18 00:45:11 Dhawal Harkawat: 2014-11-14 12:59:19 very poor form of output to be given, costed me many WA's. Finally AC. Kid Algorist: 2014-10-09 02:13:49 For all those getting TLE 993960000099397 . . . [10 times] 0 Ans: 993960000099397^1 . . [10 times] If time limit exceeds, modify algorithm. Last edit: 2014-10-09 02:14:27 Yassine Fadhlaoui: 2014-09-25 00:58:32 Last edit: 2014-09-25 01:01:55 Luc: 2014-08-21 19:56:15 Got TLE because using %I64u... really annoying that it doesn't cause an error, just TLE. Got AC using %llu :) Anmol Pandey: 2014-07-20 16:35:02 Can anybody point out why am i getting TLE --Removed link-- Got ACed For anybody needing help trial division works "just look for overflows" if they are Last edit: 2014-07-20 17:05:01 `Ak: 2014-06-28 15:43:17 http://ideone.com/isG0H2 getting tle using sieve :( TIGM: 2014-06-28 10:27:18 got accepted with worst time 4.13 sec but surely trail division work :) [Lakshman]: 2014-06-13 04:57:06 @Mayur Shingote First remove the link. you should learn about factorization algorithm. http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

 Added by: Jimmy Date: 2009-10-08 Time limit: 1.138s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL NODEJS PERL6 VB.NET