#include <fstream>

using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divprim.out");
int nrprim[10000],minim[10000][10000],i,j,k,t,n,aux;
bool prim[10000];
int main()
{
        for(i=2;i<=1000;i++)
        prim[i]=true;
    for(i=2;i<=1000;i++)
     if(prim[i]==true)
{
    nrprim[i]++;
    for(j=i+i;j<=1000;j+=i)
    {
        prim[j]=false;
        nrprim[j]++;
    }
}
for(i=1;i<=1000;i++)
    for(j=0;j<=7;j++)
    if(nrprim[i]==j)
    minim[i][j]=i;
else
    minim[i][j]=minim[i-1][j];
    fin>>t;
    for(aux=1;aux<=t;aux++)
    {
        fin>>n>>k;

     fout<<minim[n][k]<<endl;
    }
    return 0;
}