/*
Scortia Claudia
Colegiul National "Andrei Saguna"
clasa a X-a
[email protected]
*/
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

int v[100001];

int nr_div_primi(int x)
{
    int d,y=x,s=0;
    for(d=2;d*d<=y;d++)
    {
        if(x%d==0)
        {
            s++;
            while(x%d==0)
                x/=d;
        }
    }
    if(x!=1)
        s++;
    return s;
}
int main()
{
    int t,i,j,x,n,k,ok;
    fin>>t;
    for(i=1;i<=t;i++)
      {
          fin>>n>>k;
          ok=0;
          if(k==0)
            fout<<1<<"\n";
          else
          {
              while(n)
          {
              if(nr_div_primi(n)==k)
              {
                  fout<<n<<"\n";
                  ok=1;
                  break;
              }
              n--;
          }
          if(ok==0)
            fout<<0<<"\n";
          }

      }

    return 0;
}