#include <stdio.h>
char x[1000009];  
int c,k,n,t,nr,i;
int ciur(int n)
{
     int d=0;
     for(i=2;i<=n;i++) x[i]=1;
     for(i=2;i<=n && d<=nr;i++)
     {
		      if (x[i]!=0)
		      {
				  c=i;
				  while(c<=n)
				  {
					     x[c]=0;
					     c+=i;
				  }
				  k++;
				  if(n%i==0)
				   d++;
		      }
     }
     if(d==nr)
      return 1;
      return 0;
 }
 int main()
 {
     freopen("divprim.in","r",stdin);
     freopen("divprim.out","w",stdout);
     scanf("%d",&t);
     int l=0;
     for(l=1;l<=t;l++)
     {
		      int j=0,g=0;
		      scanf("%d %d",&n,&nr);
		      for(j=n;j>=1;j--)
		       if(ciur(j)==1)
			{
				     g=1;
				     printf("%d\n",j);
				     break;
			}
		       if(g==0)
			printf("0\n");
     }
     return 0;
}