// Craciun Catalin
//  Infoarena
//   DivPrim

#include <iostream>
#include <ctime>
#include <cmath>
#include <fstream>
#include <cstring>

#define DBG 1
#define NMax 1000005

using namespace std;

ifstream f("divprim.in");
ofstream g("divprim.out");

bool A[NMax];

void ciur() {
	
	memset(A, 1, sizeof(A));
	
	A[0] = 0;
	A[1] = 0;
	
	for (int i=3;i<=NMax;i+=2) {
		if (A[i] == 1) {
			for (int j=i+i;j<=NMax;j+=i) {
				A[j] = 0;
			}
		}
	} 
}

int solve(int n, int div) {
	
	if (div == 0)
		return 1;
	
	for (int i=n;i>=1;i--) {		
		int lim = sqrt(i);
		int divizoriPrimi = 0;
		
		if (A[i] && div == 1)
			return i;
	
		if (i % 2 == 0) {
			divizoriPrimi++;
			
			if (i/2 % 2 != 0) {
				if (A[i/2])
					divizoriPrimi++;
			}
		}
			
		for (int j=3;j<=lim && divizoriPrimi <= div;j+=2) {
			if (i%j == 0 && A[j]) {
				divizoriPrimi++;
				if (A[i/j] && i/j != j)
					divizoriPrimi++;
			}
		}
		
		if (divizoriPrimi == div)
			return i;
	}
	
	return 0;
}

void read() {
	
	int t;
	f>>t;
	for (int i=1;i<=t;i++) {
		int n, div;
		f>>n>>div;
		g<<solve(n, div)<<'\n';
	}
	
	f.close();
	g.close();
}

int main() {
	
#ifdef DBG
	float one = clock();
#endif //DBG
	
	ciur();
	read();
	
#ifdef DBG
	cout<<"\n\nTimpul in care s-a efectuat executia este "<<(clock()-one)/CLOCKS_PER_SEC;
#endif // DBG
	
	return 0;
}