N = 10**9
from math import gcd
def make():
    n, m = map(int, input().split())
    n %= N
    m %= N
    r = N - m
    g = gcd(n, N)
    if r % g != 0:
        print(-1)
        return
    r //= g
    n //= g
    M = N // g
    ans = r * pow(n, -1, M) % M
    if ans == 0:
        ans = M
    print(ans)
    return

for _ in range(int(input())):
    make()