#include <stdio.h>

int c[1000001];
int d[10][1000010];
int main()  {
    int t, n, k;
    FILE *fin, *fout;
    fin = fopen("divprim.in", "r");
    fout = fopen("divprim.out", "w");
    fscanf(fin, "%d", &t);
    for(int i=2; i<=1000000; i++)  {
        if(c[i]==0)  {
            for(int j=2*i; j<=1000000; j+=i)
            c[j]++;
            c[i]=1;
        }
    }
    for(int i=1; i<=7; i++)  {
        for(int j=1; j<=1000000; j++)  {
            if (c[j]==i) d[i][j]=j;
            else d[i][j]=d[i][j-1];
        }
    }
    for(int i = 0; i<t; i++)  {
        fscanf(fin, "%d%d", &n, &k);
        fprintf(fout, "%d\n", d[k][n]);
    }
    return 0;
}