#include<cstdio>
#define MM 1000100
#define STOP 1000000
using namespace std;
FILE *in,*out;

int div[MM],mat[8][MM];
int v[8]={0,0,0,0,0,0,0,0};
int nr1,nr2,nr3,nr4,nr5,nr6,nr7;

void ciur(){
    int i,j;
    for(i=4;i<=STOP;i+=2)
        div[i]++;
    div[2]=1;
    for(i=3;i<=STOP;i+=2)
        if(div[i]==0)
            for(j=i;j<=STOP;j+=i)
                div[j]++;
    return  ;
}

void matrice(){
    int j,i;
    nr1=nr2=nr3=nr4=nr5=nr6=nr7=0;
    for(i=2;i<MM;i++)
        mat[div[i]][++v[div[i]]]=i;
    return ;
}

void rezolvare(int n,int k){
    int loc=0,pas=1<<20;
    while (pas!=0){
        if(loc+pas<=v[k])
            if(mat[k][loc+pas]<=n)
                loc+=pas;
        pas/=2;
    }
    if(loc!=0)
        fprintf(out,"%d\n",mat[k][loc]);
    else fprintf(out,"0\n");

    return ;
}

int main(){
    in=fopen("divprim.in","r");
    out=fopen("divprim.out","w");
    ciur();
    matrice();

    int T,n,k;
    fscanf(in,"%d",&T);
    while (T--){
        fscanf(in,"%d%d",&n,&k);
        rezolvare(n,k);
    }
    fclose(in);
    fclose(out);
    return 0;
}