Description

给你一个数 n (1 < n <= 1000000) ,求 n! (n的阶乘)的质因数分解形式,质因数分解形式为 n=p1^m1*p2^m2*p3^m3…… * 这里 p1 < p2 < p3 < …… 为质数 * 如果 mi = 1, 则 ^ mi 就不需要输出

Input

输入是多case的,每行一个数n,1 < n <= 1000000,当n等于0时输入结束

Output

每个n输出一行,为它的质因数分解形式

Sample Input

6 7 0

Sample Output

6=2^4*3^2*5 7=2^4*3^2*5*7

Author

windy7926778