#include <cstdio>
#define DIM 1000005
using namespace std;

int a[DIM];
int v[8][DIM];

int caut( int n, int k ){

    int i = 0;
    int pas = 1 << 20;

    while( pas ){
        if( i + pas <= v[k][0] && v[k][i+pas] <= n  )
          i += pas;
        pas /= 2;
    }

    if( v[k][i] <= n && i > 0 ) return v[k][i];
    return 0;
}

int main()
{

    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);

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

    a[0] = a[1] = 0;
    for( i = 2; i * i <= DIM; ++i ){
        if( !a[i] ){
            a[i]++;
            for( j = 2 * i; j <= DIM; j += i )
              a[j]++;
        }
    }


    for( i = 1; i <= DIM; ++i ){
        v[a[i]][v[a[i]][0]+1] = i;
        v[a[i]][0]++;
    }


    scanf("%d",&t);
    for(  i = 1; i <= t; ++i ){
        scanf("%d%d",&n,&k);
        printf("%d\n",caut( n, k ));
    }


    return 0;
}