def solve(x):
    for a in range(1, int(x ** 0.5) + 1):
        if x % a:
            continue
        if a <= k and x / a <= k:
            return False
    return True

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    ans = []
    for x in range(n, max(0, n - 282), -1):
        if solve(x):
            print(x)
            break
    else:
        print(-1)