#include <cstdio>
using namespace std;
const int NMAX=1000000;
int nr[NMAX+1];
int ndiv[8][NMAX+1];
void div()
{
    int i,j;
    for(i=2;i<=NMAX;i++)
      if(nr[i]==0)
        for(j=i;j<=NMAX; j+=i)
            nr[j]++;
}
int main()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);

    int t, i,j, n,k;

    div();
    for(i=0; i<=NMAX; i++)
        ndiv[0][i]=1;

    for(i=1;i<=7;i++)
       for(j=2;j<=NMAX; j++)
             if(nr[j]== i)
               ndiv[i][j]=j;
            else
                ndiv[i][j]=ndiv[i][j-1];


    scanf("%d", &t);
    for(i=1; i<=t; i++)
    {
        scanf("%d%d", &n, &k);
        printf("%d\n", ndiv[k][n]);
    }
    return 0;
}