#include<stdio.h>
#include<string.h>
#define M 100001
char c[M];
long t,n;
int k;
void ciur(long p)
{long i,j;
 memset(c,'1',p);
 for(i=2;i<=p;i++)
      if(c[i]=='1') for(j=i;j<=p;j+=i)
			  if(i!=j) c[j]='0';
}
int main()
{int ok,i,j,r;
 FILE*f=fopen("divprim.in","r");
 FILE*g=fopen("divprim.out","w");
 fscanf(f,"%ld",&t);
 ciur(M);
 for(i=1;i<=t;i++)
	{fscanf(f,"%ld %d",&n,&k);
	 ok=0;
	 while(n&&!ok)
		{if(n%2==0) r=1;
		 else r=0;
		 for(j=3;j<=n/2;j+=2)
			if(n%j==0&&c[j]=='1') r++;
		 if(r==k) ok=1;
		 else n--;}
	 if(ok) fprintf(g,"%ld\n",n);
         else fprintf(g,"0\n");}
 fcloseall();
 return 0;
}