def make_divisors(n): lower_divisors , upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] T=int(input()) for _ in range(T): N,K=map(int,input().split()) if N>K*K: print(N) continue if N<=K: print(-1) continue for i in range(N,K,-1): div = make_divisors(i) f = True for d in div: if d<=K and i//d<=K: f = False break if f: print(i) break if not f: print(-1)