#include <fstream>

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

int t,n,i,d[1000001],x,k,j,mat[8][1000001];
int main()
{
    d[1]=0;
    for(i=2;i<=1000000;++i)
    if(d[i]==0)
    for(j=1;i*j<=1000000;++j) d[i*j]++;
    for(i=1;i<=7;++i)
    for(j=1;j<=1000000;++j)
    if(d[j]==i) mat[i][j]=j;
         else mat[i][j]=mat[i][j-1];
    f>>t;
    for(i=1;i<=t;++i)
    {
        f>>x>>k;
        g<<mat[k][x]<<"\n";
    }
}