m@main=readLn>>=putStrLn.f>>m
f n=a n++'=':tail(n#2)
1#_=""
n#p|p*p>n='*':a n
n#p=n!0where o!x|o`mod`p>0=x%('*':a p)++o#(p+1);n!x=div n p!(x+1)
0%p=""
1%p=p
x%p=p++'^':a x
a=show