There are N people, every day they devide into some groups to have a party, and the people in each group is the same. And further more, in a cycle, the number of people of a group is different every day. give you the number of days D in the cycle, you should find the value of N. If there are more than one solution, find the minimum one.
Input:
The number of days D in the cycle(D<10000). The input is end with EOF.
Output:
For each test case, ouput one line, the number N, as the multiples of its prime number factor. small to large. see the sample output.
Sample Input:
12
8
Sample Output:
2^2 * 3^1 * 5^1
2^3 * 3^1