#include <stdio.h>
#include <stdlib.h>

int ciur[1000000];
int main()
{
  FILE *fin, *fout;

  int t;
  int n, k;
  int i, j;

  fin = fopen ( "divprim.in", "r" );
  fscanf ( fin, "%d", &t );


  ciur[0] = ciur[1] = 0;
  for ( i = 2; i <= 1000000; i ++ ){
     if ( ciur[i] == 0 )
       for ( j = i; j <= 1000000; j += i )
          ciur[j]++;
  }

  fout = fopen ( "divprim.out", "w" );
  for ( i = 1; i <= t; i ++ ){
     fscanf ( fin, "%d%d", &n, &k );
     n--;
     while ( n > 0 && ciur[n] != k )
        n--;
     fprintf ( fout, "%d\n", n );
  }
    return 0;
}