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

std::vector<int> cnt[KMAX];
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=0;i<KMAX;++i)
		cnt[i].push_back(0);
	for(i=1;i<NMAX;++i)
	{
		j=nrDivs(i);
		if(j<KMAX)
			cnt[j].push_back(i);
	}
}

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

	precalc();
	fscanf(f, "%d", &_);
	do
	{
		fscanf(f, "%d%d", &N, &K);
		l=0;
		r=(int)cnt[K].size();
		while(r-l>1)
		{
			mid=(l+r)>>1;
			if(cnt[K][mid]<=N)
				l=mid;
			else
				r=mid;
		}
		fprintf(g, "%d\n", cnt[K][l]);
	}while(--_);

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