#include <stdio.h>

#define MAX 1000000

long int ciur[MAX], div[MAX];
long int v[MAX];
int m[MAX][10];
long int i, j, k, n;
int p, gasit;
int t, nr;

int main()
{
	FILE *f = fopen ("divprim.in","r");
	FILE *g = fopen ("divprim.out","w");
	fscanf (f,"%d", &t);
	
	
	for (i=2;i<=1000000;i+=2)        
		v[i]++; 
        
	for (i=3;i<=1000000;i+=2) 
	{
		if(v[i]==0)            
			for(j=i;j<=1000000;j+=i) 
				v[j]++;        
	}       
   
	for(i=1;i<=1000000;i++)    
	{        
		for(j=0;j<=7;j++)            
			m[i][j]=m[i-1][j];        
		m[i][v[i]]=i;    
	}    
   
	for(i=1;i<=t;i++) 
	{
		fscanf(f,"%ld %ld\n",&n,&k); 
		fprintf(g,"%d\n",m[n][k]); 
	} 
	
	fclose(g);
	fclose(f);
	return 0;
}