def main():
    n, k = map(int, input().split())
    for now in range(n, k, -1):
        t = int(n // now)
        f = 0
        while t * t <= now and t <= k:
            if not now % t:
                if now // t <= k:
                    f = 1
                    break
            t += 1
        if not f:
            return now
    return -1


for _ in range(int(input())):
    print(main())