#include<cstdio>

char ciur[1000001];

int main(){
  int t,n,k,i,j;

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

  //ciur-modificat pt problema noastra!! :-)
  for(i=2;i<=1000000;i++)
    if(ciur[i]==0)
      for(j=i;j<=1000000;j+=i)
        ciur[j]++;

  scanf("%d",&t);
  for(i=1;i<=t;i++){
    scanf("%d%d",&n,&k);
    j=n;
    while(ciur[j]!=k&&j>1)
      j--;
    if(j==1)
      printf("0\n");
    else
      printf("%d\n",j);
  }

  return 0;
}