# include <fstream>
# include <cstring>
# include <iostream>
# include <vector>
# define nmax 1000005
# define kmax 7
using namespace std;
ifstream fi("divprim.in");
ofstream fo("divprim.out");
unsigned short D[nmax];
bool b[nmax];
int P[nmax][kmax];
int main(void)
{
    int t,n,k;
    memset(b,1,sizeof(b));
    b[1]=D[1]=0;
    for (int i=2;i<nmax;++i)
      if (b[i])
        {
           D[i]=1;
           for (int j=2*i;j<nmax;j+=i) ++D[j],b[j]=0;
        }
    P[0][0]=P[0][1]=P[0][2]=P[0][3]=P[0][4]=P[0][5]=P[0][6]=P[0][7]=0;
    for (int i=1;i<nmax;++i)
       for (int j=0;j<8;++j)
           if (D[i]==j)
              P[i][j]=i;
           else
              P[i][j]=P[i-1][j];
    for (fi>>t;t;fi>>n>>k,fo<<P[n][k]<<"\n",--t);
    fo.close();
}