#include <fstream>
#include <vector>

using namespace std;

ifstream cin("divprim.in");
ofstream cout("divprim.out");

const int DIM=1000000;

int n;
int ciur[DIM]={0};
vector<int> baze;
vector<int> exp;

void buildCiur(){
    for(int i=2;i*i<=DIM;i++){
        if(ciur[i]==0){
            for(int j=i*i;j<=DIM;j+=i){
                ciur[j]=1;
            }
        }
    }
}

int calculateDivizori(int nr){
    int cnt=0;
    for(int i=2;i<DIM;i++){
        if(ciur[i]==0 && nr%i==0){
            baze.push_back(i);
            while(nr%i==0){
                cnt++;
                nr/=i;
            }
            exp.push_back(cnt);
            cnt=0;
        }
    }
    return baze.size();
}

int main() {
    cin>>n;

    buildCiur();

    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        int left=2,right=a,mid=0,sol=-1,divizori=0;
        while(left<=right){
            mid=left+(right-left)/2;
            divizori= calculateDivizori(mid);
            if(divizori==b){
                sol=max(sol,mid);
                left=mid+1;
            }
            else if(divizori<b){
                left=mid+1;
            }
            else if(divizori>b){
                right=mid-1;
            }
        }
        if(sol==-1){
            cout<<"0"<<endl;
        }
        else{
            cout<<sol<<endl;
        }
        baze.clear();
        exp.clear();
    }
    return 0;
}