def f(x,k):
    for i in range(1,int(x**.5)+2):
        if x%i<1 and x//i<=k:return 0
    return 1
for i in range(int(input())):
    n,k=map(int,input().split());p=500
    while n*p:
        if f(n,k):print(n);break
        n-=1;p-=1
    else:print(-1)