No submission language available for this problem.

Background

Special for beginners, ^_^

Description

给定某个正整数 ​$N​$，求其质因子分解结果，即给出其因式分解表达式 ​$N​=p_1^{k_1}* p_2​^{k_2}*...*​p_m^{k_m}​$。

Format

Input

一个整数 $N$。

Output

按给定格式输出 $N$ 的质因式分解表达式，即 N=p1^k1*p2^k2*…*pm^km，其中 pi 为质因子，并要求从小到大。指数 ki 为 pi 的个数；当 ki 为 $1$ 即因子pi只有一个时不输出 ki。 当 $n=1$ 时输出 "1=1" (不包含双引号)。

Samples

1323

1323=3^3*7^2

48

48=2^4*3

Limitation

$1 ≤ n ≤ 10^{12}$ 保证所有 $n$ 的质因子小于 $2*10^{8}$(所有$2*10^{8}$)。

1s, 1024KiB for each test case.