#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;

//ciur
for(i=2;i<=1000001;i++)
	 if(a[i]==0)
	for(k=1;k*i<=1000001;k++)
  		a[k*i]=a[k*i]+1;
	
//umplem matricea
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;
}