g;t;u;f(a,n,m,p,i){t=p=m;for(i=1;i=t/-~i;)for(i=t/i,p-=t%i?0:p/i;t%i<1;t/=i);p+=--n?f(a,n,p),t:a;for(t=1;p;p/=2)t=p&1?1ll*a*t%m:t,a=1ll*a*a%m;}main(s,m,n){for(;u-t||~scanf(g="%d %d\n",&s,&m,n=!printf(g,n,u));f(s,++n,m))u=t;}
Note that non-ascii characters in the above source code will be escaped (such as \x9f).