def divisor(n): i = 1 table = [] while i * i <= n: if n%i == 0: table.append(n//i) i += 1 return min(table) T = int(input()) for _ in range(T): N,K = list(map(int,input().split())) ans = -1 for i in range(N,K,-1): if(divisor(i) > K): ans = i break print(ans)