#include<stdio.h>
#define max 1000000
int ciur[max], s, i, j, n, k, t, nr;
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	for (i=1;i*2<=max;i++)
		ciur[2*i]++;
	for (i=3;i<=max;i+=2)
		if (ciur[i]==0){
			j=1;
			while (i*j<=max){
				ciur[i*j]++;
				j++;
			}
		}
	for (nr=1;nr<=t;nr++){
		scanf("%d%d",&n,&k);
		s=0;
		for (i=n;i>1;i--)
			if (ciur[i]==k){
				printf("%d\n",i);
				s=1;
				break;
			}
		if (s==0) printf("0\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}