#include<fstream>     
 using namespace std;     
 const int N=1000001;   
 ifstream in("divprim.in");     
 ofstream out("divprim.out");  
  int mat[N][2];  
  int maxx,t,ok;  
  int prim[N];  
  char c[N]={0};   
  void citire()  
  {   
      in>>t;  
      for(int i=0;i<t;++i)  
      {  
          in>>mat[i][0];  
          in>>mat[i][1];  
          if(mat[i][0]>maxx)  
              maxx=mat[i][0];  
      }             
  }  
  void ciur()  
  {  
      c[1]=1;     
      for(int i=2; i*i<=maxx; ++i)     
          if(c[i]==0)     
              for(int j=i*i; j<=maxx; j+=i)     
                  c[j]=1;     
  }  
  void primi()  
  {  
      prim[1]=0;  
      for(int i=2;i<=maxx;++i)  
          if(c[i]==0)  
         for(int j=i;j<=maxx;j+=i)  
              prim[j]++;  
  }  
  void cautare()  
  {  
      //int j;  
      for(int i=0;i<t;++i)  
      {  
          ok=1;  
          while(mat[i][0]>=1&&ok!=0)  
          {  
              mat[i][0]--;  
              if(prim[mat[i][0]]==mat[i][1])  
              ok=0;  
          }             
         if(ok==0) out<<mat[i][0]<<"\n";  
         else out<<"0"<<"\n";  
      }  
 }  
   int main()     
   {     
       citire();  
       ciur();  
       primi();    
       cautare();  
       in.close();     
       out.close();     
       return 0;     
   }