#include<stdio.h>
#include<math.h>
#include<string.h>
#define LIM 1000000
#define NMAX 1000
FILE *in,*out;
using namespace std;
int d[1000010],p[10000],r[8][1000010];
void ciur ()
{
    int i,j;
    d[1]=0;
    for(i=2;i<=LIM;i+=2)
        d[i]=1;
    for(i=3;i<=LIM;i+=2)
        if(d[i]==0)
            for(j=i;j<=NMAX; j+=i)
                    d[j]++;
}
int main()
{
    ciur();
    int t,n,k,i,j;
    in=fopen("divprim.in","rt");
    out=fopen("divprim.out","wt");
    fscanf(in,"%d",&t);
    for(i=1;i<=7;i++)
        for(j=1;j<=LIM;j++)
            if(d[j]==i)
                r[i][j]=j;
            else
                r[i][j]=r[i][j-1];
    while(t)
        {
            fscanf(in,"%d%d",&n,&k);
            fprintf(out,"%d\n",r[k][n]);
            t--;
        }
    return 0;
}