from math import sqrt
t = int(input())

def check(a,c):
    for n in range(1,int(sqrt(a))+1):
        b = a//n
        for m in range(b//c-1,b//c+2):
            if c*m<=b<(c+1)*m:
                print(b)
                return
        if b<c:
            print(-1)
            return
            
for i in range(t):
    a,c = map(int,input().split())
    flag = 0
    if a>=10**3 or c>=10**3:
        check(a,c)
    elif c>a:
        print(-1)
    elif c == a:
        print(a)
    else:
        s = set()
        for i in range(1,a+1):
            if a//i>=c:
                s.add(a//i)
        arr = sorted(s)
        for b in arr:
            flag = 0
            for m in range(b//c,b//c+2):
                if c*m<=b<(c+1)*m:
                    print(b)
                    flag = 1
                    break
            if flag:
                break
        if flag == 0:
            print(-1)