#include <stdio.h>
#include <string.h>
#define Nmax 1000
#define IN "divprim.in"
#define OUT "divprim.out"


int viz[Nmax+1], sol[Nmax][8];

void ciur()
{
  for(long i=2; i<=Nmax; i++)
    if(!viz[i])
      for(long j=1; j*i<=Nmax; j++)
        viz[i*j]++;
        
}

void gen()
{
  for(int i=2; i<=Nmax; i++)
  {
    memcpy(sol[i],sol[i-1], sizeof sol[i]);
    
    sol[i][viz[i]] = i;
  }
}

void solve()
{
  int t,n,p;
  scanf("%d",&t);
  for(int k=0; k<t;k++)
  {
    scanf("%d %d",&n,&p);
    printf("%d\n",sol[n][p]);
  }
}

int main()
{
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
  
  ciur();
  gen();
  
  solve();
return 0;
}