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