#include<fstream.h>

long long t, n, k, m[8][1000005], nr1, nr2, nr3, nr4, nr5, nr6, nr7, nr8;
int *c=new int[1000005];

ifstream in("divprim.in");
ofstream out("divprim.out");

void ciur(int n)
{
  int i, j;
  for (i=2; i<=n; i++)
    {
       if (c[i]==0)
	{ c[i]=1;
	  for (j=2*i; j<=n; j+=i)
		c[j]++;
	}
    }
}


void calcul()
{ long long i, j;
  for(i=1;i<=8;i++) m[i][1]=0;
for(i=2;i<=900004;++i)
	{
	for(j=1;j<=8;j++) m[j][i]=m[j][i-1];
	m[c[i]][i]=i;
	}
}


int main()
{
  in>>t;
  int i, j;
  ciur(900004);
  calcul();
  for (i=1; i<=t; i++) {in>>n>>k; out<<m[k][n]<<'\n';}
  in.close();
  out.close();
  return 0;
}