#include<fstream.h>

int k[1000], rez[1000];
long n[1000], t, l;




void citire()
{
  ifstream in("divprim.in");
  in>>t;
  for (int i=1; i<=t; i++)
    in>>n[i]>>k[i];
  in.close();
}


int prim(int x)
{
  if (x==0 || x==1) return 0;
  if (x==2) return 1;
  if (x%2==0) return 0;
  for (int d=3; d*d<=x; d++)
    if (x%d==0) return 0;
  return 1;
}


int nrdiv(int x)
{
  int c=0;
  for (int i=2; i<=x/2; i++)
    if (x%i==0 && prim(i)) c++;
  return c;
}

void prelucrare(int x);

void afis()
{
  ofstream out("divprim.out");
  for (l=1; l<=t; l++)
    out<<rez[l]<<endl;
  out.close();
}

ofstream g("divprim.out");
int main()
{

  citire();
  for (l=1; l<=t; l++)
    prelucrare (n[l]);
  afis();
  return 0;

}

void prelucrare(int x)
{
  int j;

  for (j=x; j>0; j--)
    {if (nrdiv(j)==k[l] && rez[l]==0)
      rez[l]=j;
    }

}