#include <fstream>

using namespace std;
ifstream in ("divprim.in");
ofstream out ("divprim.out");
char v[1000001];
int main()
{
    int t,n,k,i,m,j,a;
    in>>t;
    for(i=2;i<=1000000;i++)
    {
        if(v[i]==0)
        {
            for(m=i;m<=1000000;m=m+i)
            {
                v[m]++;
            }
        }
    }
    for(i=1;i<=t;i++)
    {
        in>>n>>k;
        for(j=1;j<=n;j++)
            if(v[j]==k)
            a=j;
        out<<a<<'\n';
    }
    return 0;
}