#include<fstream>
using namespace std;
int v[1000005],s[1000005][8],t,n,k,i,j;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
void ciur()
{
     s[1][0]=0;
     v[0]=0;v[1]=1;
     for(i=2;i<1000005;i++)
     {
     if(!v[i])
      for(j=i;j<1000005;j+=i)
      v[j]++;
      for(j=0;j<=7;j++)
      s[i][j]=s[i-1][j];
      if(v[i]<=7)
      s[i][v[i]]=i;
     }
}


int main()
{
    fin>>t;
    ciur();
    for(i=1;i<=t;i++)
    {
    fin>>n>>k;
    fout<<s[n][k]<<"\n";
    }
    fin.close();
    fout.close();
}