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))