#include <fstream>

using namespace std;
int a[10001][101],v[100001],k[100001],lun[10001];
int main()
{ int n,i,st,mij,dr,nr,j,div,Max=0;
    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=1;i<=Max;++i) {
            div=2;
            mij=i;
            nr=0;
            while (mij>1) {
                if (mij%div==0) {
                    ++nr;
                    while (mij%div==0)
                        mij/=div;
                }
                ++div;
            }
            ++lun[nr];
            a[nr][lun[nr]]=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;
}