#include <fstream>

using namespace std;
int a[8][100001],v[100001],k[100001],lun[8],nr[1000001];
int main()
{ int n,i,st,mij,dr,Max=0,j;
    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 (nr[i]==0) {
     for (j=1;j<=Max/i;++j)
         ++nr[i*j];
        }
    for (i=1;i<=Max;++i)
    if (nr[i]<8) {
        ++lun[nr[i]];
        a[nr[i]][lun[nr[i]]]=i;
    }
    for (i=1;i<=n;++i) {
        st=1,dr=lun[k[i]];
        Max=0;
        while (st<=dr) {
            mij=(st+dr)/2;
            if (a[k[i]][mij]<=v[i]) {
                 Max=max(Max,a[k[i]][mij]);
                 st=mij+1;
            }
             else dr=mij-1;
        }
           g<<Max<<"\n";
    }
    return 0;
}