ll@t;REP(t){ll@(n,m,a,b,c,d),s=0,r=0;while(r>?=s,r>?=s+a*~-n+b*(n=(c*~-n+d)/m),n){d=m+~d;s+=(a+b)*(a<0)+d/c*a;d%=c;a^=b^=a^=b+=m/c*a;c^=m^=c^=m%=c;}wt(r);}