#include<fstream>
using namespace std;
long long int h=1000000;
int main(){
    ifstream in("divprim.in");
    ofstream out("divprim.out");
    int v[h],a[7][h];
    long long int t,n,k;
    for(long long int i=1;i<=h;i++){
        v[i]=0;
    }
    for(long long int i=2;i<=h;i++){
        if(v[i]==0){
           for(long long int j=i;j<=h;j+=i){
                v[j]++;
            }
        }
    }
    for(int i=1;i<=7;i++){
        a[i][1]=0;
    }
    for(long long int i=1;i<=7;i++){
        for(long long int j=2;j<=h;j++){
            if(v[j]==i){
                a[i][j]=j;
            }else{
                a[i][j]=a[i][j-1];
            }
        }
    }
    in>>t;
    for(long long int j=1;j<=t;j++){
        in>>n>>k;
        out<<a[k][n]<<'\n';
    }
}