#include <fstream>

using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int main()
{
    int n,i,j,k,div,nr=0,t,ci;
    in>>t;
    for(j=1; j<=t; j++)
    {
        in>>n>>k;
        i=n+1;
        while(nr!=k&&i>0)
        {
            i--;
            nr=0;
            div=2;
            ci=i;
            while(ci!=1&&i!=0)
            {
                if(ci%div==0&&i!=0)
                {
                    nr++;
                    while(ci%div==0)
                        ci/=div;
                }
                div++;
            }

        }
        out<<i<<'\n';
    }


    return 0;
}