#include <bits/stdc++.h>

const int MV = 1e6 + 5 ;

FILE *in = fopen("divprim.in", "r"), *out = fopen("divprim.out", "w") ;

std::vector<int> prime[8] ;

int sieve[MV] ;

void ciur() {
  int i, j ;
  for (i = 2; i <= MV ; i += 2) {
    sieve[i] = 1 ;
  }
  for (i = 3 ; i <= MV ; i += 2) {
    if (!sieve[i]) {
      for (j = i ; j <= MV ; j += i) {
        sieve[j] ++ ;
      }
    }
  }
}

#define INC

void comp() {
  int i ;
  for (i = 1 ; i <= MV ; ++ i) {
    prime[sieve[i]].push_back(i) ;
  }
  #ifdef INC
  for (i = 1 ; i <= 7 ; ++ i) {
    fprintf(out, "%d : ", i) ;
    for (auto it : prime[i]) {
      fprintf(out, "%d ", it) ;
    }
    fputc('\n', out) ;
  }
  #endif
}

int caut_bin(int limit, int nrdiv) {
  int pas, pos(0) ;
  for (pas = 1 << 20 ; pas ; pas >>= 1) {
    if (pas + pos < prime[nrdiv].size() && prime[nrdiv][pas + pos] <= limit)
      pos |= pas ;
  }
  return prime[nrdiv][pos] ;
}

int solve() {
  int n, k ;
  fscanf(in, "%d %d", &n, &k) ;
  int ans = caut_bin(n, k) ;
  return ans * (ans <= n) ;
}

int main() {
  ciur() ;
  comp() ;
  int querrys ;
  fscanf(in, "%d", &querrys) ;
  while (querrys --) {
    fprintf(out, "%d\n" ,solve()) ;
  }
}