X;f(m,a,x,y){a&&f(a,m%a,X=y,x-m/a*y);}main(m,a){for(;~scanf("%d%d",&a,&m);printf("%d\n",(X+m)%m))f(m,a,0,1);}