#include <stdio.h>
#include <stdlib.h>
char ciur[1000000];

int main(){
  FILE *fin, *fout;
  fin = fopen ( "divprim.in", "r" );
  fout = fopen ( "divprim.out", "w" );
  int t, n, k, d, i, j;
  fscanf( fin, "%d", &t );
  ciur [0] = ciur[1] = 0;
  for ( d = 2; d <= 1000000; d ++ ){//fac ciurul in care calculez nr de divizori primi ai numerelor pana la n
    if ( ciur[d] == 0 ){
      for ( i = d ; i <= 1000000; i += d )
        ciur[i] ++;
    }
  }
  for ( i = 0; i < t; i ++ ){
    fscanf( fin, "%d%d", &n, &k );
    j = n - 1;
    while ( j > 0 && ciur[j] != k )
      j = j - 1;
    fprintf( fout, "%d\n", j );
  }
  fclose ( fin );
  fclose ( fout );
  return 0;
}