#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int nmax=1000000;
int d[1000005],i,x,k,j,t,p,m,u,rasp;
vector<int> v[8];
int main()
{
     ifstream f("divprim.in");
     ofstream g("divprim.out");
     for(i=2;i<=nmax;i++)
      if(d[i]==0)
       for(j=i;j<=nmax;j+=i)
          d[j]++;
     for(i=1;i<=nmax;i++)
        {if(d[i]<=7) {v[d[i]].push_back(i);}}
     f>>t;
     for(i=1;i<=t;i++)
     {
         f>>x>>k;
         p=0;u=v[k].size()-1;
         while(u-p>1)
         {
             m=(p+u)/2;
             if(v[k][m]<x) p=m;
             else u=m;
         }
         if(v[k][u]>x) u--;
         rasp=v[k][u];
         if(v[k][v[k].size()-1]<x) rasp=0;
         if(x<v[k][0]) rasp=0;

         g<<rasp<<'\n';
     }
    return 0;
}