#include<stdio.h>
#include<bitset>
#include<vector>
using namespace std;
bitset<1000005> c;
vector<int> p;
int nd[1000005],sol[1000005][10];
void gen_primes()
{
	int i,j;
	c[0]=c[1]=1;
	for(i=4;i<=1000000;i+=2)
		c[i]=1;
	for(i=3;i<=1000;i+=2)
		if(!c[i])
			for(j=i*i;j<=1000000;j+=2*i)
				c[j]=1;
	p.push_back(2);
	for(i=3;i<=1000000;i+=2)
		if(!c[i])
			p.push_back(i);
}
void solve_nd()
{
	vector<int>::iterator it;int j;
	for(it=p.begin();it!=p.end();it++)
	{
		j=1;
		while((*it)*j<=1000000)
			nd[(*it)*(j++)]++;
	}
}
void get_solutions()
{
	int i,j;
	for(i=2;i<=1000000;i++)
		{
		for(j=0;j<=7;j++)
			sol[i][j]=sol[i-1][j];
		sol[i][nd[i]]=i;
		}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	gen_primes();
	solve_nd();
	get_solutions();
	int t,i,n,k;
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",sol[n][k]);
	}
	return 0;
}