#include <fstream>
using namespace std;

bool vDivPrim(int x);
int main(int argc, char *argv[]){
	int n,t;
	short int k,divPrimi;
	ifstream in;
	ofstream out;
	in.open("divprim.in");
	in>>t;
	out.open("divprim.out");
	for(int i = 0;i < t;++i){
		in>>n>>k;
		int j;
		j = --n;
		do{
			divPrimi = 0;
			for(int d = 2;d <= j/2;++d){
				if(j % d == 0){
					if(vDivPrim(d)){;
						++divPrimi;
					}
				}
			}
		--j;
		}while ((j > 0) && (divPrimi != k));
		if(divPrimi == k)
			out<<++j<<endl;
		else
			out<<"0"<<endl;
	}
	in.close();
	out.close();
	return 0;
}

bool vDivPrim(int x){
	bool prim = 0;
	if(x % 2 != 0){
		prim = 1;
		int d = 2;
		do{
			if(x % d == 0)
				prim = 0;
			++d;
		}while ((d <= x/2) && (prim == 1));
	}else if(x == 2)
		prim = 1;
	return prim;
}