def divisor(n, K):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i <= K and n//i <= K:
                return False
    return True

for _ in range(int(input())):
    N, K = map(int, input().split())

    for n in range(N, K, -1):
        if divisor(n, K):
            print(n)
            break
    else:
        print(-1)