# include <stdio.h>
int divprimi(int n){
	int i=2,nr=0;
   while (n!=1)
         {if (n%i==0)
           {nr++;
      	   while(n%i==0)
         	     n=n/i;
            }
         i++;
         }
   return nr;
   }

int prim(int n){
	int i;
   if(n==2)
   	return 1;
   if(n%2==0)
   	return 0;
   for(i=3;i*i<=n;i+=2)
   	if(n%i==0)
      	return 0;
   return 1;
}

int main (){
	int x,n,gata,i,k,d,t;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
   for (i=1;i<=t;i++)
      {scanf("%d %d",&n,&k);
       if (k==7 && n<510510) printf("%d\n",0);
           else
             if (k==7 && n>=510510) printf("%d\n",510510);

       else {if (n==1 || prim(n)) printf("%d\n",0);
             else
            {gata=0;
             for (x=n;x>1 && !gata;x--){
				 d=divprimi(x);
                 if (d==k) {gata=1;
                            printf("%d\n",x);}
                }
             if (!gata) printf("%d\n",0);
			}
	   }
        }
	return 0;
}