s,m,i,j;f(x,y){long long r=j=1,a=s,z=y=x;for(;j*j++<z;)for(y-=z%j?0:y/j;z%j<1;)z/=j;for(j=--i?f(y-=y/z%y)+y:s;r=j%2?r*a%x:r,j/=2;)a=a*a%x;i++;return r;}main(x,y){for(;~scanf(y="%d %d\n",&s,&m);printf(y,i,x))for(i=1;x%f(m);i++)x=f(m);}