T = int(input())
query = []
report = []

for _ in range(T):
    N, M = map(int, input().split())
    query.append([N, M])

for N, M in query:
    sign = True
    for i in range(2, max(N, M)+1):
        if N % i == 0 and M % i == 0:
            report.append(i)
            sign = False
            break
    if sign:
        report.append(-1)


[print(i) for i in report]