#include <stdio.h>
#include <math.h>
#define Nmax 1000005
#define Kmax 9
#define Tmax 100005

int p[Nmax];
int a[Nmax][Kmax];

void ciur(){
	int i,j,k;
   int sqNmax=sqrt(Nmax-5);
   for(i=2;i<=sqNmax;++i)
     if(p[i]==0){
       for(j=2*i;j<Nmax;j+=i)
         p[j]++;
 //      p[i]=1;
     }

   a[1][0]=1;
   for(i=2;i<Nmax;++i){
     for(k=0;k<8;++k) a[i][k]=a[i-1][k];
     a[i][p[i]]=i;
   }
}

void read(){
	int t,n,k;
   freopen("divprim.in","r",stdin);
   freopen("divprim.out","w",stdout);
   scanf("%d",&t);
   for(; t; --t){
   	scanf("%d%d",&n,&k);
 //     if(k!=0)
       printf("%d\n",a[n][k]);
//      else printf("%d\n",1);
   }
   fclose(stdin); fclose(stdout);
}

int main(){
   ciur();
 	read();
   return 0;
}