#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int nmax=1000000, kmax=7;

int sol[nmax+2][kmax+2], v[nmax+2];

int main(){
    v[1]=1;
    for(int i=2;i<=nmax;i++){
        if(v[i]==0){
            for(int j=i;j<=nmax;j+=i){
                v[j]++;
            }
        }
    }
    for(int i=2;i<=nmax;i++){
        for(int j=1;j<=kmax;j++){
            sol[i][j]=sol[i-1][j];
        }
        sol[i][v[i]]=i;
    }
    int t,n,k;
    fin>>t;
    for(int i=1;i<=t;i++){
        fin>>n>>k;
        fout<<sol[n][k]<<"\n";
    }
    return 0;
}