#include <fstream>
using namespace std;
ifstream cin("divprim.in");
ofstream cout ("divprim.out");
int a[1000005];

int main ()
{
    int i,j,t;
    for (i=4;i<1000001;i+=2)
        ++a[i];
    for (i=3;i<1000000;i+=2)
        if (!(a[i]))
            for (j=i;j<1000001;j+=i)
                ++a[j];
    for (cin>>t;t;--t)
    {
        cin>>i>>j;
        while(i>-1&&a[i--]!=j);
        cout<<i+1<<'\n';
    }
    return 0;
}