#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int NMAX=1000000;
bitset <NMAX+5> prim;
vector <int>nrprim;
int nr_divizori[NMAX+5];
void ciur_eratosthene(int n)
{
    int i, j;
    prim[1]=1;
    for(i=2;i<=n;i++)
    {
        if(prim[i]==0)
        {
            nrprim.push_back(i);
            for(j=i*2;j<=n;j=j+i)
                    prim[j]=1;
        }
    }
}
void divizori_primi(int n)
{
    int d, nr=0, i=0, cn;
    bool ok=0;
    cn=n;
    d=nrprim[i];
    while(d*d<=n and n>1)
    {
        ok=0;
        while(n%d==0)
        {
            ok=1;
            n=n/d;
        }
        if(ok==1)
            nr++;
         i++;
         d=nrprim[i];
    }
    if(n>1)
        nr++;
     nr_divizori[cn]=nr;

}
int cautare_binara(int val, int n)
{
    int st=1,dr, med, solutie=0;
    dr=n;
    while(st<=dr)
    {
        med=(st+dr)>>1;
        if(nr_divizori[med]==val)
        {
            solutie=med;
            st=med+1;
        }
        else
        {
            if(nr_divizori[med]<val)
                st=med+1;
            else
                dr=med-1;
        }
    }
    return solutie;
}
int cautare(int val, int n)
{
    int i;
       for(i=n;i>=2;i--)
       {
           if(nr_divizori[i]==val)
            return i;
       }
       return 0;
}

int main()
{
    int i, t, k, n;
    nr_divizori[1]=0;
    ciur_eratosthene(NMAX+5);
    for(i=2;i<=NMAX;i++)
       divizori_primi(i);
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        //int s=cautare(k, n);
        //if(s<=n)
         //   fout<<s<<"\n";
       // else
           // fout<<"0"<<"\n";
        fout<<cautare(k, n)<<"\n";
    }
    return 0;
}