#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 ct,n,k,t,j,i,ok;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    prim();
   for(int i=1;i<=NMAX;i++)
    for(int 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;
}