#include<stdio.h>
int verprime(int n,int m,int k){
	m=0;
	for(int j=2;j<=n;++j){
		int s=0;
		for(int q=2;q<=j;++q){
			int p=1;
			int d=2;
			while(p && d*d<=j)
				if(j%d==0)
					p=0;
				else
					d++;
			if(p==1)
				s=1;
			else{
			int p=1;
			int d=2;
			while(p && d*d<=q)
				if(q%d==0)
					p=0;
				else
					d++;
			if(p==1 && j%q==0)
				s++;
			}
		}
		if(k==s)
			m=j;
		if(k<s && m==j)
			m=0;
	}
	printf("%d\n",m);
}
int main(){
	int t,n,k,i,m;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	for(i=0;i<t;++i){
		scanf("%d",&n);
		scanf("%d",&k);
		verprime(n,m,k);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}