#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;
}
int main(){
	int t,n,k,nr=0,i,x,e=-1;
	int v[100],p[100]={0};
	/*v[0]=2;
	v[1]=3;
	v[2]=5;
	v[3]=7;
	v[4]=11;
	v[5]=13;
	v[6]=17;
	v[7]=19;
	v[8]=23;
	v[9]=29;
	v[10]=31;
	v[11]=37;
	v[12]=41;
	*/freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	for(int j=0;j<t;j++){
		scanf("%d%d",&n,&k);
		for(x=4;x<=n;x++){
			for(i=2;i<x;i++)
				if (prim(i)==0)
					if(x%i==0&&x!=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;
}