from math import gcd, lcm MOD = 10**9 def inverse(n, d, MOD): return n * pow(d, -1, MOD) % MOD for _ in range(int(input())): N, M = map(int, input().split()) X = (-M)%MOD if X == 0: print(lcm(N, MOD)//N) continue GCD = gcd(N, MOD) if X%GCD != 0: print(-1) continue GCD = gcd(N, MOD, X) n = N//GCD m = MOD//GCD x = X//GCD print(inverse(x, n, m))