#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
ifstream f("divprim.in");
ofstream g("divprim.out");
const int NMAX=1000000;
const int KMAX=8;
int T;
unsigned char NrDiv[NMAX+1];
vector<int> B[KMAX];
void precalc()
{
     int i,j;
     for (i=0;i<KMAX;++i) B[i].pb(0);
     B[0].pb(1);
     for (i=2;i<=NMAX;++i)
     {
       if (NrDiv[i]==0)
         for (j=i;j<=NMAX;j+=i) NrDiv[j]++;
       B[NrDiv[i]].pb(i);
     }
}
void solve()
{
     int N,K;
     for (f>>T;T;T--)
     {
         f>>N>>K;
         vector<int>::iterator p=upper_bound(B[K].begin(),B[K].end(),N);
         g<<*(p-1)<<'\n';
     }
}
int main()
{
    precalc();
    solve();
    return 0;
}