for _ in range(int(input())):
    N,K=map(int,input().split())
    b1=False
    while K<N:
        b2=False
        for i in range(1,int(N**0.5)+2):
            if N%i==0 and max(i,N//i)<=K : b2=True ; break
        if b2 : N-=1 ; continue
        print(N) ; b1=True ; break
    if not b1 : print(-1)