#include <stdio.h>

int n,k,i,j,a[1000010],b[1000010][8],t;

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	for (i=2; i<=1000000; ++i)
	{
		if (a[i]>0) continue;
		a[i]=1;
		for (j=i*2; j<=1000000; j+=i) 
			++a[j];
	}
	for (i=1; i<=1000000; ++i)
		for (j=1; j<=7; ++j)
		{
			b[i][j]=b[i-1][j];
			if (a[i]==j) b[i][j]=i;
		}
	for (scanf("%d",&t); t; --t)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",b[n][k]);
	}
	return 0;
}