Today, Arxor gets a task. There are N cakes and N Boxes, and Arxor has to put these cakes into Boxes. It’s easy, isn’t it? Now Arxor wonders how many ways he can finish this task. By the way, Arxor is weak in big number, so you only have to output the decomposition quality factors of the answer. The format is as follow: p₁^m₁*p₂^m₂*p₃^m₃…. Here p₁ < p₂ < p₃ < …. If m_i = 1, the ‘^ m_i’ should be neglected. E.g. you should output 2^2*3*5^2 if the answer is 300.

　　The input file contains several test cases.
　　Each test case contains one line with a single integer N, 1 < N <= 1,000,000, the number of cakes.
　　N = 0 indicates the end of input and should not be processed.

　　For each test case, output “Case #:” on the first line, '#' is the number of the test case. Then output the decomposition quality factors of the answer on the next line.