#include <stdio.h>
using namespace std;
const int NMAX = 1e6;
const int DIV_MAX = 7;
char divprim[NMAX+1];
int div_max[DIV_MAX][NMAX+1];
static inline int Max(int a,int b) {
    return a>b?a:b;
}
void build() {
    int i,j;
    for(i=2;i<=NMAX;i+=1+i%2)
        if(divprim[i]==0)
            for(j=i;j<=NMAX;j+=i)
                divprim[j]++;
    
    for(i=1;i<=DIV_MAX;i++)
        for(j=1;j<=NMAX;j++)
            if(divprim[j]==i)
                div_max[i-1][j]=Max(div_max[i-1][j-1],j);
            else
                div_max[i-1][j]=div_max[i-1][j-1];
}
int main(int argc, const char * argv[]) {
    FILE *fin,*fout;
    int n,k,t;
    build();
    fin=fopen("divprim.in","r");
    fscanf(fin,"%d",&t);
    fout=fopen("divprim.out","w");
    while(t--) {
        fscanf(fin,"%d%d",&n,&k);
        fprintf(fout,"%d\n",k==0?1:div_max[k-1][n]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}