#include<iostream>
#include<fstream>


using namespace std;


int v[100001];


int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int n,i,x,y,c,ok,j;
    for(i=2;i<=100000;i++)
    {
        if(v[i]==0)
        {
            v[i]=1;
            c=i+i;
            while(c<=100000)
            {
                v[c]++;
                c=c+i;

            }
        }
    }

   //for(i=1;i<=10;i++)
    //g<<v[i]<<" ";
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        for(j=x;j>=1;j--)
        if(v[j]==y)
        break;

        g<<j<<endl;
    }


    return 0;

}