#include<fstream.h>

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

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 mat()
{
  long long i;
  for (i=1; i<=1000004; i++)
    {
       switch(c[i])
	 {
	   case 1: { nr1++; m[1][nr1]=i;break;}
	   case 2: { nr2++; m[2][nr2]=i;break;}
	   case 3: { nr3++; m[3][nr3]=i;break;}
	   case 4: { nr4++; m[4][nr4]=i;break;}
	   case 5: { nr5++; m[5][nr5]=i;break;}
	   case 6: { nr6++; m[6][nr6]=i;break;}
	   case 7: { nr7++; m[7][nr7]=i;break;}
	   case 8: { nr8++; m[8][nr8]=i;break;}
	 }

    }
  m[1][0]=nr1;
  m[2][0]=nr2;
  m[3][0]=nr3;
  m[4][0]=nr4;
  m[5][0]=nr5;
  m[6][0]=nr6;
  m[7][0]=nr7;
  m[8][0]=nr8;

}

# int binary_search(int val)  
# {  
#     int i, step;  
#     for (step = 1; step < N; step <<= 1);  
#     for (i = 0; step; step >>= 1)  
#         if (i + step < N && A[i + step] <= val)  
#            i += step;  
#     return i;  
# }  
*/

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


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