#include <cstdio>
#define filein "divprim.in"
#define fileout "divprim.out"
#define MIL 1000000
using namespace std;

int dp[MIL+1];
int a[8][MIL+1];
int T;
int N,K;

void Erathostenes();

int main()
{
    Erathostenes();
    register int i,j;
    for (i=1; i<=7; i++)
    {
        for (j=1; j<=MIL; j++)
        {
            if (dp[j]==i)
                a[i][j]=j;
            else a[i][j]=a[i][j-1];
        }
    }
    FILE *in,*out;
    in=fopen(filein,"r");
    out=fopen(fileout,"w");
    fscanf(in,"%d",&T);
    for (i=1; i<=T; i++)
    {
        fscanf(in,"%d%d",&N,&K);
        fprintf(out,"%d\n",a[K][N]);
    }
    fclose(in);
    fclose(out);
    return 0;
}

void Erathostenes()
{
    a[0][1]=1;
    register int i,j;
    for (i=2; i<=MIL; i++)
    {
        a[0][i]=1;
        if (dp[i]==0)
        {
            for (j=i+i; j<=MIL; j+=i)
                dp[j]++;
            dp[i]=1;
        }
    }
}