#include <iostream>
#include <cstdio>
#define Nmax 1000001
using namespace std;

int a[Nmax][8],prim[Nmax];

int main()
{
   freopen("divprim.in","r",stdin);
   freopen("divprim.out","w",stdout);

   int t,n,k,i,j;

   for(i=2;i<=Nmax;i++)
    if(!prim[i])
     for(j=i;j<=Nmax;j+=i)
      ++prim[j];

   for(i=2;i<=Nmax;i++)
    for(j=0;j<=7;j++)
        if(prim[i]==j)
          a[i][j]=i;
        else
          a[i][j]=a[i-1][j];

   scanf("%d",&t);

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



}