#include <iostream>
#include <cstdio>
#define Nmax 1000001
#define FOR(i,a,b) for(i=a;i<=b;++i)
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,Nmax)
    if(!prim[i])
     for(j=i;j<=Nmax;j+=i)
      ++prim[j];

   FOR(i,2,Nmax)
    FOR(j,0,7)
        if(prim[i]==j)
          a[i][j]=i;
        else
          a[i][j]=a[i-1][j];

   scanf("%d",&t);

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



}