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