#include <fstream>
#include <vector>
#define M 1000005
#define mp make_pair
#define pb push_back
#include <algorithm>
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
vector<pair<int ,int> > sol;
bool ciur[M] ;
int dp[M];
void eratostene(){
    ciur[0]=ciur[1]=1;
    dp[0]=dp[1]=0;
    for(int i=2;i<M;i++){
        if(ciur[i]==0){
            for(int j=i+i;j<M;j+=i){
                ciur[j]=1;
                dp[j]++;
            }
            dp[i]++;
        }
    }
    for(int i=0;i<M;i++){
       sol.pb(mp(dp[i] ,i)); 
    }
    sort(sol.begin() ,sol.end());
}
int cmp(int n,pair<int ,int> p){
    return n-p.first;
}
int main(){
    eratostene();
    int t;
    cin>>t;
    //sort(sol.begin() ,sol.end());
    /*for(int i=0;i<M;i++){a
        cout<<sol[i].first<<" "<<sol[i].second<<'\n';
    }
    */
    //return 0;
    while(t--){
        int n,k;
        cin>>n>>k;
        vector<pair<int ,int > >::iterator it = upper_bound(sol.begin() ,sol.end() ,k ,cmp);
        //cout<<(*it).first<<" "<<(*it).second;
        bool sem=0;
        if(it!=sol.end()){
            for(vector<pair<int ,int > >::iterator i=it;i>=sol.begin() ;i--){
                if((*i).second<n && (*i).first==k){
                    cout<< (*i).second;
                    sem=1;
                    break;
                }
            }
        }
        if(sem==0){
            cout<<0;
        }
        cout<<endl;
    }
}