# include <fstream>
# include <cstring>
# include <iostream>
# include <vector>
# define nmax 1000005
# define kmax 8
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;
        }
    D[0]=0;
    for (int i=0;i<8;++i) P[0][i]=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];
                  if (D[P[i][j]]!=j) P[i][j]=0;
              }
    for (fi>>t;t;fi>>n>>k,fo<<P[n][k]<<"\n",--t);
    fo.close();
}