while 1:
 R,m=map(int,raw_input().split());t=r=m;T=1
 while R:t,T=T,t-r/R*T;r,R=R,r%R
 print t%m