#include <fstream>
#include <math.h>
using namespace std;
int main()
{
	int N,K,T,k,i,ok,div,prim=0,max=0,k1;
	ifstream fin("divprim.in");
	ofstream fout("divprim.out");
	fin>>T;
	for(k=1;k<=T;k++) {
		fin>>N>>K;
		for(i=1;i<=N;i++) {
			prim=0;
			for(k1=1;k1<=i;k1++) {
				if(i%k1==0) {
					ok=1;
					if(k1==1) ok=0;
					else if(k1==2) ok=1;
					else if(k1%2==0) ok=0;
					else {
						div=3;
						while(div<=k1/2) {
							if(k1%div==0) ok=0;
							div+=2;
						}
					}
					if(ok==1) prim++;
				}		
		}
			if(prim==K) {
				if(i>max) max=i;
				else max=max;
			}
		}
		fout<<max<<"\n";
		
	}
	
	return 0;
}