def gcd(a, b):
  if a == 0:
    return b
  if b == 0:
    return a
  while a != b:
    if a > b:
      a = a - b
    else:
      b = b - a
  return a
def lcd(a, b):
  g = gcd(a, b)
  if g == 1:
    return -1

  for i in range(2, g + 1):
    if g % i == 0:
      return i

  return -1
t = int(input())
for _ in range(t):
  n, m = map(int, input().split())
  print(lcd(n, m))