g;t;u;a;f(m,n,p,i){t=p=m;for(i=2;t%i?i=t/(t/-~i),p-=t%i?0:p/i:(t/=i)-1;);p+=--n?f(p,n),t:a;n=a;for(t=1;p;p/=2)t=p&1?1ll*n*t%m:t,n=1ll*n*n%m;}main(m,n){for(;u-t||~scanf(g="%d %d\n",&a,&m,n=!printf(g,n,u));f(m,++n))u=t;}