#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;
vector <int>numere[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++;
     numere[nr].push_back(cn);

}
int cautare_binara(int val, int n)
{
    int st=0,dr, med, solutie=0;
    dr=numere[val].size()-1;
    while(st<=dr)
    {
        med=(st+dr)>>1;
        if(numere[val][med]<=n)
        {
            if(numere[val][med]>solutie)
             solutie=numere[val][med];
            st=med+1;
        }
        else
                dr=med-1;
    }
    return solutie;
}

int main()
{
    int i, t, k, n;
    ciur_eratosthene(NMAX+5);
    for(i=2;i<=NMAX;i++)
       divizori_primi(i);
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        fout<<cautare_binara(k, n)<<"\n";
    }
    return 0;
}