#include<stdio.h>
#include<math.h>

#define X 1000001

char prim[X];

int fprim(int n)
{
    if(!prim[n]) return 1;
	
	int i,k=0,rad=sqrt(n);
	
	if(n%2==0) k++;
	
	for(i=3; i<=n; i+=2)
		if(!prim[i])
			if(n%i==0) k++;
	
	return k;
}

int main()
{
	 freopen("divprim.in","r",stdin);
	 freopen("divprim.out","w",stdout);
	 
	 int ok,n,k,x,i,j;
	 for(i=3; i<=X; i+=2)
		 if(!prim[i]) for(j=i*2; j<=X; j+=i) prim[j]=1;
	 
	 scanf("%d",&n);
	
	for(; n; --n)
	{
		scanf("%d %d",&x,&k);
		ok=0;
		for(i=x; i>=2; --i)
			if(fprim(i)==k) { ok=1; break; }
		if(ok) printf("%d\n",i);
		  else printf("0\n");
	}
	
	return 0;
}