//#include "stdafx.h"
#include <iostream>
#include <fstream>
#define NM 1000001
FILE *in=fopen("divprim.in","r");
FILE *out=fopen("divprim.out","w");
char p[NM];
void sieve(char (&p)[NM])
{
	int i,j;
	for(i=2;i*i<=NM;i++)
		if(!p[i])
			for(j=i;j<=NM;j=j+i)
				if(j!=i) p[j]++;
}
int main()
{
	int t,n,k,i;
	sieve(p);
	fscanf(in,"%d",&t);
	for(i=1;i<=t;i++)
	{
		fscanf(in,"%d%d",&n,&k);
		while(p[n]!=k&&n)
			n--;
		fprintf(out,"%d\n",n);
	}
	fclose(in); fclose(out);
	return 0;
}