s,m,i,j;f(x){long long a=s,b=x,c=x,d=2;for(;c%d<1?c/=d,b-=c%d?b/d:0:d*d++<c;);d=i?i--,f(b-=b/c%b),j+b:s;i++;for(j=1;j=d%2?a*j%x:j,d/=2;)a=a*a%x;}main(x,y){for(;~scanf(y="%d %d\n",&s,&m);printf(y,i,j))for(i=0;f(m),x%j;)x=j;}
Note that non-ascii characters in the above source code will be escaped (such as \x9f).