#include <stdio.h>
int prim(int i){
	int j;
	if (i==2)
		return 0;
	for(j=2;j*j<=i;j++)
		if(i%j==0)
			return -1;
	return 0;
}
void divizori(int *v){
	int i,j=1;
	v[0]=2;
	for(i=3;j<100;i+=2)
		if(prim(i)==0){
			v[j]=i;
			j++;
		}
}

int main(){
	int t,n,k,nr=0,i,x,e=-1;
	int v[100],p[100]={0};
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	divizori (v);
	for(int j=0;j<t;j++){
		scanf("%d%d",&n,&k);
		if (k==0)
			for(x=n;x>=0;x--)
				if(prim(x)==0){
					printf("%d\n",x);
					x=-1;
				}
		if(k>0){
			for(x=4;x<=n;x++){
				for(i=0;i<100;i++)
					if(x%v[i]==0&&x!=v[i])
						nr++;
				if(nr==k){
					e++;
					p[e]=x;
				}
			nr=0;
			}
		if(e==-1)
			printf("0\n");
		else
			printf("%d\n",p[e]);
		for(i=0;i<100;i++)
			p[i]=0;
		}
	}
	return 0;
}