T = int(input()) NK = [tuple(map(int, input().split())) for _ in range(T)] # エラトステネスの篩 def eratos(N,K): primes = [True] * (N+1) primes[0], primes[1] = False, False for i in range(1, K+1): a = i if a * a > N:break b = 1 for _ in range(K): primes[a] = False a += i if a > N:break ret = [num for num, is_prime in enumerate(primes) if is_prime] return ret for N,K in NK: P = eratos(N,K) if len(P) == 0: print(-1) else: print(P[-1])