#include<fstream.h>
ifstream f("divprim.in");
ofstream g("divprim.out");
int a[1000001],b[1000001][8],t,i,j,k;
int main(){
f>>t;

//ciur
for(i=2;i<=500001;i++)
	 if(a[i]==0)
	for(k=1;k*i<=100001;k++)
  		a[k*i]=a[k*i]+1;
	
//umplem matricea
for(i=2;i<=1000000;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<=t;i++)
{ f>>j>>k;
	g<<b[j][k]<<'\n';
}		
return 0;
}