#include <iostream>
#include <fstream>
using namespace std;
int ciur[1000005],mat[1000005][9];
void ci(){
    ciur[1]=0;
    for(int i=2;i<=1000005;++i){
        if(ciur[i]==0){
           for(int j=i;j<=1000005;j+=i)
                ciur[j]++;
        }
    }
}
void ma(){
    for(int i=0;i<=7;i++){
        mat[1][i]=0;
    }
    for(int i=2;i<=1000005;i++){
        for(int j=0;j<=7;j++){
            mat[i][j]=mat[i-1][j];
        }
        mat[i][ciur[i]]=i;
    }
}
int main()
{
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
    ci();
    ma();
    int n,i,t,k;
    cin>>t;
    for(i=1;i<=t;i++){
        cin>>n>>k;
        cout<<mat[n][k]<<'\n';
    }
    return 0;
}