///Nume:Roman Bianca-Gabriela
///Scoala:C.N.I. Grigore Moisil
///Clasa:a 10a
///Email:[email protected]

#include <iostream>
#include <fstream>
using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int divizori(int x)
{
    int nr=0;
    if(x==1)
        return 0;
    if(x%2==0)
    {
        nr++;
        while(x%2==0)
            x/=2;
    }
    for(int d=3;d*d<=x;d+=2)
        if(x%d==0)
    {
        nr++;
        while(x%d==0)
            x/=d;
    }
    if(x>1)
        nr++;
   return nr;
}


int main()
{
    int t,n,k;
    f>>t;
    for(int i=1;i<=t;i++)
    {
        int ok=0;
        f>>n>>k;
        for(int j=n;j>=1 && ok!=1;j--)
            if(divizori(j)==k)
             {
                 ok=1;
                 g<<j<<" "<<"\n";
             }
       if(ok==0)
          g<<"0"<<" "<<"\n";
    }

    return 0;
}