#include <fstream>
#include <iostream>
#include <ctime>
using namespace std;

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