For your math homework this week, your teacher gave you five large numbers, and asked you to find their prime factors. However, these numbers aren’t *nearly* large enough for someone with knowledge of programming like yourself. So, you decide to take the factorial of each of these numbers. Recall that `N`! (`N` factorial) is the product of the integers from 1 through `N`. It’s your job now to create a program to help you do your homework.

The input file **DATA2.txt** will contain 5 test cases. Each test case contains a number `N` (2 ≤ `N` ≤ 10000).

The output file **OUT2.txt** will contain 5 lines of output, each representing the prime factorization of factorial of the given number, which should be of the form: `p`_{1}^`e`_{1} * `p`_{2}^`e`_{2} * ... * `p`_{k}^`e`_{k} where `p`_{1}, `p`_{2}, ..., `p`_{k} are the distinct prime factors of the given number in increasing order, and `e`_{1}, `e`_{2}, ..., `e`_{k} are their exponents.

```
2
3
5
10
20
```

```
2^1
2^1 * 3^1
2^3 * 3^1 * 5^1
2^8 * 3^4 * 5^2 * 7^1
2^18 * 3^8 * 5^4 * 7^2 * 11^1 * 13^1 * 17^1 * 19^1
```