#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define NMAX 1000005
using namespace std;
int nrprim[NMAX];
int divprimi[NMAX];
int sol[NMAX][8];
void prim()
{int i,j;
 for (i=1;i<=NMAX;i++)
    nrprim[i]=1;
 for (i=2;i<=NMAX;i++)
   if ((nrprim[i]) )
    {divprimi[i]=1;
   for (j=2*i;j<=NMAX;j+=i)
    {nrprim[j]=0;divprimi[j]++;}
        }}      
 
int main()
{int n,k,t,j,i;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    prim();
   for(i=1;i<=NMAX;i++)
    for(j=1;j<=7;j++)
     {if(divprimi[i]==j)
       sol[i][j]=i;
      else sol[i][j]=sol[i-1][j]; 
            } 
    for (i=1;i<=t;i++)
    {
        scanf("%d %d",&n,&k);
    
       printf("%d\n",sol[n][k]);
    }
    
return 0;
}