#include<fstream.h>
ifstream f("divprim.in");
ofstream g("divprim.out");
int a[1000005],b[1000005][9];
long long k,i,t,j;
int main()
{f>>t;
for(i=2;i<=1000001;i++)
  if(a[i]==0)
   for(k=1;k*i<=1000001;k++)
     a[k*i]=a[k*i]+1;
for(i=2;i<=1000001;i++)
  for(k=1;k<=7;k++){
    if(a[i]==k)
	 b[i][k]=i;
	else b[i][k]=b[i-1][k];}
for(i=1;i<=1000001;i++)
  b[i][0]=1;				
for(i=1;i<=t;i++)
{f>>j>>k;
g<<b[j][k]<<'\n';}		
return 0;}