gcd = lambda a, b: b if a == 0 else gcd(b, a % b) if b != 0 else a
lcd = lambda a, b: -1 if (g := gcd(a, b)) == 1 else next(i for i in range(2, g + 1) if g % i == 0)
for _ in range(int(input())):
    print(lcd(*map(int, input().split())))