from math import isqrt def solve(): n, k = map(int, input().split()) while k <= n: for d in range(1, isqrt(n)+1): if n%d==0 and d <= k and n//d <= k: break else: print(n) return n -= 1 print(-1) return t = int(input()) for i in range(t): solve()