import math


def solve():
    N, K = map(int, input().split())

    for n in range(N, 0, -1):
        for div in range(1, min(K, math.isqrt(n)) + 1):
            if n % div != 0:
                continue

            if n // div > K:
                continue

            break
        else:
            print(n)
            return

    print(-1)


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()