#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

short h[1000002];

int main()
{
    int m=0,n,t,i,j,k,nr[100001],nrd[100001];
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>nr[i]>>nrd[i];
        if(nr[i]>m) m=nr[i];
    }
    for(i=2;i<=m;i++)
    {
        if(!h[i])
        {
            h[i]=1;
            for(j=2*i;j<=m;j+=i)
                h[j]++;
        }
    }
    for(i=1;i<=t;i++)
    {
        j=nr[i];
        while(nrd[i]!=h[j] and j)
        {
            j--;
        }
        g<<j<<'\n';
    }
    return 0;
}