s,m,i,j;f(x,y,z){j=y=x;for(z=2;j%z<1?j/=z,y-=j%z?y/z:0:z*z++<j;);z=i?i--,f(y-=y/j%y),j+y:s;i++;y=s;for(j=1;j=z%2?1LL*j*y%x:j,z/=2;)y=1LL*y*y%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;}