#include<stdio.h>
#include<string.h>
#define M 1000001
char c[M];
long t,n;
int k;
void ciur(long p)
{int 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)
		{r=0;
                 if(n%2==0) r++;
                 for(j=3;j<=n/2;j+=2)
			if(n%j==0) if(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;
}