#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000000
#define MAXK 7

unsigned char ciur[MAXN+1];
int mat[MAXK+1][MAXN];
int cnt[MAXK+1];

int main() {
    FILE *fin, *fout;
    int t, n, k, i, d, st, dr, mijl;
    for( d = 2; d <= MAXN; d++ )
      if( ciur[d] == 0 )
          for( i = d; i <= MAXN; i += d )
            ciur[i]++;
    for( i = 1; i <= MAXN; i++ )
      if( ciur[i] <= 7 )
        mat[ciur[i]][cnt[ciur[i]]++] = i;
    fin = fopen( "divprim.in", "r" );
    fout = fopen( "divprim.out", "w" );
    fscanf( fin, "%d", &t );
    for( i = 0; i < t; i++ ) {
      fscanf( fin, "%d%d", &n, &k );
      st = 0;
      dr = cnt[k];
      while( dr - st > 1 ) {
        mijl = ( st + dr ) / 2;
        if( mat[k][mijl] > n )
          dr = mijl;
        else
          st = mijl;
      }
      if( n >= mat[k][st] )
        fprintf( fout, "%d\n", mat[k][st] );
      else
        fprintf( fout, "0\n" );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}