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

int prim(long x){int i;
		  if((x==0)||(x==1))return 0;
		  if(x==2)return 1;
		  if(x>2)for(i=2;i<=sqrt(x);i++)if(x%i==0)return 0;
		  return 1;
		  }
int div(int x){int k=0,i;
	      for(i=2;i<=x;i++) if((x%i==0)&&(prim(i)==1))k++;
	      return k;
	      }

int main()
{long t=0,i=0,k=0,n=0,ok=0;

freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);

scanf("%ld",&t);
for(i=1;i<=t;i++){
	   n=0;k=0;
	   scanf("%ld %ld",&n,&k);
	   ok=1;
	   for(i=n-1;i>0;i--)if(div(i)==k){printf("%ld",i);ok=0;break;}
	   if(ok==1)printf("0");
	   }

return 0;
}