#include <fstream>
#include <vector>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
const int NMAX=1000000;
int nrdiv[NMAX+5];
vector <int>numere[NMAX+5];
void ciur_eratosthene(int n)
{
    int i, j;
    for(i=2;i<=n;i++)
    {
        if(nrdiv[i]==0)
        {
            for(j=i;j<=n;j=j+i)
                    nrdiv[j]++;
        }
    }
    for(i<=2;i<=n;i++)
        numere[nrdiv[i]].push_back(i);
}
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);
    fin>>t;
    for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        fout<<cautare_binara(k, n)<<"\n";
    }
    return 0;
}