#include<iostream.h>
int c[1000000];
int mat[7][500000];
void generate()
{
	int i,j;
	for(i=2;i<=1000000;++i)
		if(!c[i])
			for(j=i;j<=1000000;j+=i)
				++c[j];
    for(i=2;i<=1000000;++i)
		mat[c[i]][++mat[c[i]][0]]=i;
}
int binary_search(int k,int x)
{
	int st=1,dr=mat[k][0],m;
	while(st!=dr)
	{
		m=((st+dr)>>1);
		if(x<=mat[k][m])
			dr=m;
		else
			st=m+1;
	}
	if(mat[k][st]>x)
		--st;
	if(st)
	return mat[k][st];
	else
		return 0;
}
int main()
{
	int n,k,t;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	generate();
	while(t)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",binary_search(k,n));
		--t;
	}
	return 0;
}