T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    ans = -1
    for x in range(1,N+1):
        flag = True
        for div in range(1,N+1):
            if div * div > N or div > K:
                break
            if x % div == 0 and x // div <= K:
                flag = False
                break
        if flag:
            ans = x
    print(ans)