#include <iostream>
#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int ciur[1000001],i,t,j,a,m,var,nr,n[100002],k[100002];
int main()
{
    f>>t;
    m=0;
    for(i=1;i<=t;i++)
    {
        f>>n[i]>>k[i];
          if(n[i]>m)
            m=n[i];
    }
    for(i=1;i<=m;i++)
        ciur[i]=0;
    ciur[1]=1;
    for(i=4;i<=m;i=i+2)
        ciur[i]=1;
    for(i=3;i<=m;i=i+2)
    {
        for(j=i;j<=m/i;j=j+2)
            ciur[i*j]=1;
    }

  for(i=1;i<=t;i++)
  {
      for(j=n[i];j>=1;j++)
      {
          a=1;
          nr=0;
          while(a<=n[i])
          {
         if(ciur[a]==0)
         {
             if(j%ciur[a]==0)
                nr++;
         }
         a++;
          }
         if(nr==k[i])
         {
             g<<j;
             j=-1;
         }


      }
      if(j!=-1)
      g<<0;
      g<<"\n";
  }
    return 0;
}