#include <cstdio>
#include <fstream>

using namespace std;

int c[1048576],e[8][1048576];

int main ()
{
	
	for(int i=2;i<=1000000;i+=2)
		c[i]=1;
	for(int i=3;i<=1000000;i+=2)
		if(!c[i]){
			c[i]=1;
			for(int j=i<<1;j<=1000000;j+=i)
				++c[j];
			}
	for(int i=1;i<=1000000;++i)
		e[0][i]=1;
	for(int i=1;i<8;++i)
		for(int j=1;j<=1000000;++j){
			e[i][j]=e[i][j-1];
			if(c[j]==i)
				e[i][j]=j;
			}
	ifstream in ("divprim.in");
	freopen ("divprim.out","w",stdout);
	int t,n,k;
	for(in>>t;t;--t){
		in>>n>>k;
		printf("%d\n",e[k][n]);
		}
	
	return 0;}