from math import*
from bisect import*
t=int(input())
N=100000
spf=[0]*(N+1)
prime=[]
for m in range(2,N+1):
 if spf[m]<1:spf[m]=m;prime+=[m]
 for p in prime:
  if p>spf[m] or p*m>N:break
  spf[p*m]=p
for _ in range(t):
  n,k=map(int,input().split())
  ans=-1
  i=bisect_left(prime,isqrt(n))
  a=prime[i]
  b=n//a
  if(k<a or k<b)and 1<=a and 1<=b and a*b<=n:
    ans=max(ans,a*b)
  if i:
    a=prime[i-1]
    b=n//a
    if(k<a or k<b)and 1<=a and 1<=b and a*b<=n:
      ans=max(ans,a*b)
  m=10**6
  s=[1]*m
  for i in prime:
    j=max(k//i,2)*i
    if j<=k:
      j+=i
    while k<j<k+m:
      s[j-k]=0
      j+=i
  for i in range(1,m):
    if s[i]:
      a=i+k
      b=n//a
      if(k<a or k<b)and 1<=a and 1<=b and a*b<=n:
        ans=max(ans,a*b)
  print(ans)