#include<stdio.h>
#include<math.h>
#include<string.h>
#define NMAX 1000
#define LIM 1000000
int div[1000010],prime[10000],res[8][1000010];
void ciur_div()
{
    int i,j,depan;
    div[1]=0;
    for(i=2;i<=LIM;i+=2)
        div[i]=1;
    for(i=3;i<=LIM;i=i+2)
        if(div[i]==0)
            for(j=i;j<=LIM;j=j+i)
                {
                    div[j]++;
                    if(j==930930)
                        depan=0;
                }
}

int main()
{
    ciur_div();
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int tc,n,k,i,j,nu,flag;
    scanf("%d",&tc);
    for(i=1;i<=7;i++)
        for(j=1;j<=LIM;j++)
            if(div[j]==i)
                res[i][j]=j;
            else
                res[i][j]=res[i][j-1];
    while(tc)
        {
            scanf("%d%d",&n,&k);
            printf("%d\n",res[k][n]);
            tc--;
        }
    return 0;
}