while 1: a,b=map(int,raw_input().split());x=B=b;y=1 while a:x,y=y,x-b/a*y;b,a=a,b%a print x%B