#include<stdio.h>
#define MAX 1000001
long v[MAX],n,t,k;
void ciur()
{
	int i,j;
	for(i=2;i+i<=MAX;++i)
	{
		if(!v[i])
		{v[i]=1;
		for(j=i*2;j<MAX;j+=i)
		++v[j];
		}
	}
}
int main()
{
	ciur();
	FILE*f=fopen("divprim.in","r");
	fscanf(f,"%ld",&t);	
	long i;
	FILE*g=fopen("divprim.out","w");
	for(;t;--t)
	{
		fscanf(f,"%ld%ld",&n,&k);
		for(i=n;i>=0;--i)
			if(v[i]==k){fprintf(g,"%d\n",i);i=-2;}
		if(i==-1)fprintf(g,"0\n");
	}
	fclose(f);
	fclose(g);
	return 0;
}