//DIVPRIM INFOARENA
#include <fstream>
using namespace std;
#define NMAX 1000004

ifstream fin("divprim.in");
ofstream fout("divprim.out");
int T[8][NMAX+100];

void erat(){
      int i,j;
      for (i=2;i<=NMAX;i++)
         	if (T[0][i]==0){
            	for (j=i;j<=NMAX;j+=i)
                     	T[0][j]++;
            }
}

void precalc(){
      int i,j,k;
      for (k=1;k<=7;k++)
      	for (i=1;i<=NMAX;i++)
                  if (T[0][i]==k)	T[k][i]=i;
                  else 			T[k][i]=T[k][i-1];
}

int main(){
	int n,i,k,t;
	fin>>t;
      erat();
      precalc();
      for (i=1;i<=t;i++)
      {
       	fin>>n>>k;
            fout<<T[k][n]<<'\n';
      }
	fout.close();
      return 0;
}