T = int(input()) NK = [tuple(map(int, input().split())) for _ in range(T)] # エラトステネスの篩 def eratos(n): primes = [True] * (n+1) primes[0], primes[1] = False, False for i in range(2, int(n**0.5)+1): if primes[i]: for j in range(i**2, n+1, i): primes[j] = False primes[1] = True ret = [num for num, is_prime in enumerate(primes) if is_prime] return ret def is_prime(i): if i <= 1: return False for j in range(2, int(i**0.5) + 1): if i % j == 0: return False return True P = eratos(10 ** 5) for N,K in NK: ans = 0 for a in P: b = N//a # print(a,b) if a <= K and b <= K:continue if is_prime(b): ans = max(ans,a*b) print(ans if ans != 0 else -1)