//Ilie Dumitru
#include<cstdio>
#include<vector>
const int KMAX=8;
const int NMAX=1000001;

int cnt[KMAX][NMAX];
int divizor[NMAX];

int nrDivs(int n)
{
	int c=0, d=0;
	while(n!=1)
	{
		if(divizor[n]!=d)
			++c, d=divizor[n];
		n/=d;
	}
	return c;
}

void precalc()
{
	int i, j;
	std::vector<int> prime;

	for(i=2;i<NMAX;i+=2)
		divizor[i]=2;
	for(i=3;i<NMAX;i+=2)
	{
		if(!divizor[i])
		{
			divizor[i]=i;
			prime.push_back(i);
		}
		for(j=0;j<(int)prime.size() && i*prime[j]<NMAX;++j)
			divizor[i*prime[j]]=prime[j];
	}

	for(i=1;i<NMAX;++i)
	{
		for(j=0;j<KMAX;++j)
			cnt[j][i]=cnt[j][i-1];
		j=nrDivs(i);
		cnt[j][i]=i;
	}
}

int main()
{
	FILE* f=fopen("divprim.in", "r"), *g=fopen("divprim.out", "w");
	//FILE* f=stdin, *g=stdout;
	int _, N, K;

	precalc();
	fscanf(f, "%d", &_);
	do
	{
		fscanf(f, "%d%d", &N, &K);
		fprintf(g, "%d\n", cnt[K][N]);
	}while(--_);

	fclose(f);
	fclose(g);
	return 0;
}