#include<fstream>

using namespace std;

#define nmax 1000005

int t,k,n,nr_div[nmax],solutie[nmax][10];

int main(void){
    ifstream fin("divprim.in");
    ofstream fout("divprim.out");
    fin>>t;
    solutie[1][0]=0;
    for(int i=2;i<nmax;++i){
      if (nr_div[i] == 0)
              for(int j=i;j<nmax;j+=i)
                        ++nr_div[j];
              for (int m=0;m<=7;++m)
                    solutie[i][m]=solutie[i-1][m];
              if(nr_div[i]<=7)
                    solutie[i][nr_div[i]]=i;
                          }          
    while (t>0){
           fin>>n>>k;
           fout<<solutie[n][k]<<"\n";
           t--;
           }
 
    fin.close();
    fout.close();
    return 0;  
}