import sys
input = sys.stdin.readline

T=int(input())

for tests in range(T):
    N,K=map(int,input().split())

    ANS=-1

    for i in range(N,K,-1):
        sq=round(i**(1/2))

        for j in range(1,min(sq,N)+1):
            if i%j==0:
                k=i//j

                if 1<=j<=K and 1<=k<=K:
                    break

        else:
            ANS=i
            break

    print(ANS)