#include<stdio.h>
#define N 1000000
int t,n,k,p[N],nrp[N];
//p[i] == 0 if i is prime  
void ciur(int n)
{
	int i,j;  
	p[2]=0;
    for (i=2;i<=n;i++)   
    	if (p[i]==0)			
			for (j=i+i;j<=n;j+=i)   
				p[j]=1;  
}
void upvec(int n)
{
	int i,j;
	for(i=2;i<=n;i++)
		if(p[i]==0)
			for(j=i+i;j<=n;j+=i)
				nrp[j]++;
}
void read_solve()
{
	int i1,i,ok;
	scanf("%d",&t);
	ciur(N);
	upvec(N);
	for(i1=0;i1<t;i1++)
	{
		scanf("%d%d",&n,&k);
		ok=1;
		for(i=n-1;i>=1&&ok;i--)
			if(nrp[i]==k)
			{
				printf("%d\n",i);
				ok=0;
			}
		if(ok)
			printf("0\n");
	}
}
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	read_solve();
	return 0;
}