Q=int(input())
from math import isqrt
for _ in range(Q):
  N,K=map(int,input().split())
  result=-1
  for x in range(N,N-100,-1):
    if x<=0:
      break
    y=isqrt(x)
    ans=True
    for k in range(1,y+1):
      if x%k==0:
        z=x//k
        if z<=K:
          ans=False
    if ans==True:
      result=x
      break
  print(result)