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

int ciur[1+MAXN];
int d[1+MAXN][8];
int main(){
    int i, j, n, k;
    FILE*fi,*fo;
    fi=fopen("divprim.in","r");
    fo=fopen("divprim.out","w");
    ciur[0]=ciur[1]=0;
    for(i=2;i<=MAXN;i++)
        if(ciur[i]==0){
            for(j=i;j<=MAXN;j+=i)
                ciur[j]++;
        }
    for(i=1;i<=MAXN;i++){
        for(j=0;j<=7;j++)
            d[i][j]=d[i-1][j];
        d[i][ciur[i]]=i;
    }

    int t;
    fscanf(fi,"%d", &t);
    for(int i=0;i<t;i++){
        fscanf(fi,"%d%d", &n, &k);
        if(k!=0)
            fprintf(fo,"%d\n", d[n][k]);
        else{
            fprintf(fo,"1\n");
        }
    }
    fclose(fi);
    fclose(fo);
    return 0;
}