#include <fstream>
#include <vector>
#define nmax 1000001
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
vector <int> nd[9];
int d[1000004];
int prim[1000004];
int main()
{int n,i,j,x,y;
for(i=2;i<=nmax;i++)
{
    if(prim[i]==0)
    {
        d[i]++;
        for(j=i+i;j<=nmax;j+=i)
        {
            prim[j]=1;
            d[j]++;
        }
    }
}
for(i=1;i<=8;i++)
    nd[i].push_back(0);
for(i=1;i<=nmax;i++)
{
    nd[d[i]].push_back(i);
}
in>>n;
for(i=1;i<=n;i++)
{
    in>>x>>y;
    out<<*(lower_bound(nd[y].begin(),nd[y].end(),x)-1)<<'\n';
}
    return 0;
}