#include <fstream>
#include<algorithm>
#define NMAX 1000005
using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
struct vect{
    int x,y;
};
vect v[NMAX];
bool f(vect a,vect b){
    return a.y<b.y;
}
void ciur(int n){
    
    for(int i=2;i<=n;i++){
        if(!v[i].y){
            v[i].y=1;
            for(int j=i+i;j<=n;j+=i){
                v[j].y++;
                }
            }
        }
    for(int i=1;i<=n;i++){v[i].x=i;}
}

int main()
{
  int t;
  cin>>t;
    ciur(NMAX);
  for(int i=0;i<t;i++){
      int n,k;
      cin>>n>>k;
      sort(v+1,v+n+1,f);int vct[n+1]={0};
      
     for(int i=1;i<=9;i++){vct[i]=v[i].y;}
      auto sus=upper_bound(vct+1,vct+n+1,k);
      int val=sus-vct-1;
      cout<<v[val].x<<"\n";
  }
      
  return 0;
}