#include<stdio.h>
#define N 1000000
int i,j,t,n,k;
int a[7][1000010];
int c[N];


void precalcul()
{
	int i;
	
	for(i=2;i<N;i++)
		if(c[i]==0)
			for(j=i;j<N;j+=i)
				++c[j];
	
/*	for(i=1;i<N;i++)
		printf("%d\n",c[i]);
	*/
	for(i=1;i<N;i++)
		a[c[i]][++a[c[i]][0]]= i;

}
int main()

{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	bool ok = false;
	precalcul();
	
	for(i=1;i<=t;i++)
	{
		scanf("%d",&n);
		
		scanf("%d",&k);
		j = 0;
		for(j=1;a[k][j]<n;j++);
			if(j == 1)
				printf("0\n");
			else
				printf("%d\n",a[k][j-1]);
		
	}


return 0;

}