#include <stdio.h>

int v[1000001],m[1000001][8];
int i,j,h,k,t,n;

int main ()
{
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    
    for (i=2;i<=1000000;i++)
        if (v[i]==0) 
           for (j=i;j<=1000000;j=j+i) v[j]++;
           
    for (i=1;i<=1000000;i++)
        for (j=1;j<=7;j++){
            if (v[i]==j) m[i][j]=i;
            else m[i][j]=m[i-1][j];
            }
    for (i=1;i<=1000000;i++) m[i][0]=1;
    
    scanf ("%d",&t);
    for (h=1;h<=t;h++){
        scanf ("%d %d",&n,&k);
        printf ("%d\n",m[n][k]);
        }
    
    return 0;
}