#include <iostream>
#include <fstream>
using namespace std;
int t[1000000],x[1000000];
int cautbin(long long st,long long dr,int n){long long m;
    if(st<=dr){m=(st+dr)/2;
        if(n==x[m])return x[m];
        else if(n>x[m])
        return cautbin(m+1,dr,n);
        else return cautbin(st,m-1,n);}

    else
    return x[dr];

}
void zero(){
    for(int i=0;i<1000000;i++)t[i]=0;
}
ifstream fin("fact.in");
ofstream fout("fact.out");

int main()
{
    int T,n,i,j,k,p=1,m=0,v[]={2,3,5,7,11,13,17};
    fin>>T;
    while(T>0){T--;
  fin>>n>>k;
  for(i=0;i<k;i++)p=p*v[i];
  zero();
  for(i=0;i<k;i++){j=p;
  while(j<=1000000)
  {t[j]=1;j=j*v[i];}
  }
  for(j=1;j<=1000000;j++)
  if(t[j]==1){x[m++]=j;}

fout<<cautbin(1,m,n)<<endl;}


    return 0;
}