#include<fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int m[1000002][8],p[1000002],i,j,n,a,b;
int main()
{
    for(i=2;i<=1e6;m[i][p[i]]=i,++i) {
        if(!p[i])
            for(j=i;j<=1e6;++p[j],j+=i);
        for(j=1;j<8;m[i][j]=m[i-1][j],++j);
    }
    for(f>>n;n;--n)
        f>>a>>b,g<<m[a][b]<<'\n';
    return 0;
}