#include<fstream> 
using namespace std;
ifstream f("divprim.in"); ofstream g("divprim.out");
const int Nmax=1000001;
int i,j,n,k,t,d,nr[Nmax],a[Nmax][9]; 
int main()
{   d=2; 
    while(d<Nmax)
	{   for(i=d;i<Nmax;i+=d) nr[i]++; 
        d++; 
        while(nr[d]) d++; 
    } 
    for(i=1;i<=Nmax;i++) a[i][nr[i]]=i; 
    for(i=1;i<=Nmax;i++) 
        for(j=1;j<=7;j++) 
            if(a[i-1][j]>a[i][j]) a[i][j]=a[i-1][j]; 
    f>>t; 
    for(i=1;i<=t;i++)
	{	f>>n>>k;
		g<<a[n][k]<<'\n';
    } 
	g.close(); return 0; 
}