#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

#define n 1000005 

int v[n];
vector<int> m[8]; 

inline void erat()
{
   m[0].push_back(1);  
   int i,j;
   for(i=2;i<n;i++)
   {
     if(!v[i]) 
       for(j=i;j<n;j+=i)
         v[j]++;
     m[v[i]].push_back(i);
   }     
}

int main()
{
    erat();
    ifstream cin("divprim.in");
    ofstream cout("divprim.out");
       
    int t,i,x,k,cap,coada,mijl,rasp;
    cin>>t;
    
    for(i=0;i<t;i++)
    {
       cin>>x>>k;
       
       rasp=0;
       cap=0;
       coada=m[k].size()-1;
       mijl=coada>>1;
       
       while(cap<=coada)
       {            
          if(m[k][mijl]<=x)
          {               
             if(m[k][mijl]>rasp)
               rasp=m[k][mijl];
             cap=mijl+1;                   
          }        
          else
             coada=mijl-1;
          mijl=(cap+coada)>>1;
       }
       cout<<rasp<<'\n';
    }
    
    cin.close();
    cout.close();
    return 0;
}