import math
T=int(input())
for _ in range(T):
    N,M=map(int, input().split())
    p=10**9
    try:
        g = math.gcd(p-M, N)
        N%=p
        M%=p
        t=(p-M)//g*pow(N//g,-1,p)%p
        print(t)
    except:
        print(-1)