import numpy as np
X=10**9
I=np.loadtxt(open(0),"q",skiprows=1).astype("O").T
I//=np.gcd(*I)
for N,M in I.T:
	try:print(-M*pow(N,-1,X)%X)
	except:print(-1)