/*Popescu Alexandru Iulian ;Colegiul national Dr. Ioan Mesota;clasa 10;[email protected]*/
#include <iostream>
#include <fstream>
using namespace std;
int v[1000000];
int main()
{ ifstream f("divprim.in");
  ofstream g("divprim.out");
    int N,K,T,i,j;
        f>>T;
        for(i=2;i<1000000;i++)
             if(v[i]==0)
              for(j=2;j<=1000000/i;j++)
                 v[i*j]++;
          for(i=1;i<=T;i++)
              { f>>N>>K;
                int OK=0;
            for(j=N;j>=2&&OK==0;j--)
                 if(v[j]==K){g<<j<<'\n';OK=1;}
                  if(OK==0) g<<0<<'\n';
            }




    f.close();
     g.close();
    return 0;
}