#include <fstream>

using namespace std;
int a[8][1000001],nr[8],v[100001],k[100001],x[1000001];
bool ciur[1000001];
int main()
{ int n,i,st,dr,mij,Max=0,j,sol;
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    f>>n;
    for (i=1;i<=n;++i) {
        f>>v[i]>>k[i];
        Max=max(Max,v[i]);
    }
    for (i=2;i<=Max;++i)
    if (!ciur[i])
        for (j=1;i*j<=Max;++j) {
            ciur[i*j]=1;
            ++x[i*j];
        }
    x[1]=0;
    for (i=1;i<=Max;++i)
       if (x[i]<=7)
        ++nr[x[i]],a[x[i]][nr[x[i]]]=i;
    for (i=1;i<=n;++i) {
        sol=0;
        st=1,dr=nr[k[i]];
        j=k[i];
        while (st<=dr) {
            mij=(st+dr)/2;
            if (a[j][mij]<=v[i]) sol=max(sol,a[j][mij]),st=mij+1;
            else dr=mij-1;
        }
        g<<sol<<'\n';
    }
    return 0;
}