//Divizori Primi
#include<fstream>
using namespace std;
   int t,n,j,i,k,a[1000005],v[1000005][11];  
   int main()
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
{   
     fin>>t;
     v[1][0]=0;
    for (i=2;i<1000005;i++)      
{ 
      if(!a[i])
    for (j=i;j<1000005;j+=i)
      a[j]++;      
    for(j=0;j<=7;j++)
      v[i][j]=v[i-1][j];
    if(a[i]<=7)
      v[i][a[i]]=i;
}      
    for(i=1;i<=t;t++)
{ 
    fin>>n>>k;
    fout<<v[n][k]<<'\n';
}
    fin.close();
    fout.close();
    return 0;
}