#include <stdio.h>
#include <algorithm>
#define N 1000005
#define NRP 100001

using namespace std;

FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");

int i,j,T,nr,n,k,p[NRP],nrp[N],st[N][10];
bool b[N];

void ciur()
{
    int i,j;
    p[++p[0]]=2;
    for(i=3;i<=N;i+=2)
     if(!b[i])
     {
         for(j=3*i;j<=N;j+=2*i)
          b[j]=1;
         p[++p[0]]=i;
     }
}

int main()
{
    fscanf(f,"%d",&T);
    ciur();
    for(i=2;i<=N;i++)
     if(!(nrp[i]))
      for(j=i;j<=N;j+=i) nrp[j]++;
    for(i=1;i<=N;i++)
    {
        for(j=0;j<=7;j++) st[i][j]=st[i-1][j];
        st[i][nrp[i]]=i;
    }
    for(int t=1;t<=T;t++)
    {
        fscanf(f,"%d%d",&n,&k);
        fprintf(g,"%d\n",st[n][k]);
    }
    return 0;
}