#include <fstream>

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