## 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
```

 < Previous 1 2 3 4 5 Next > SK Raina: 2013-02-02 14:01:53 I Am Use FOR Loop -> TLE But Use WHILE Loop Than -> AC Which Better .... ????? saket diwakar: 2013-01-24 18:51:04 AC in first attempt.....:) (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-04-21 07:58:15 for this problem, Trial Division (without precomputing) is 4 times faster than Trial Division (with precomputing) :-O