#include <cstdio>

int v[7][1000001];

int c[1000001];

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

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


int main()
{
    int t,n,k;
    ciur();
    fscanf(f,"%d",&t);
    for ( int i=1;i<=t;++i ){
        fscanf(f,"%d%d",&n,&k);
        int p=0;
        for ( int pas=1<<24;pas;pas/=2 )
            if ( p+pas<=v[k][0]&&v[k][p+pas]<=n )
                p+=pas;
        if ( v[k][1]>n )
            fprintf(h,"0\n");
        else
            fprintf(h,"%d\n",v[k][p]);
    }
    return 0;
}