#include<iostream>
#include<fstream>
using namespace std;
int is_prim(int n){
    if(n == 0 || n == 1) return 0;
    if(n == 2) return 1;
    if(n % 2 == 0) return 0;
    for(int i = 3; i * i <= n; i+=2)
       if(n % i == 0) return 0;
        return 1;
}
int main(){
	
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int t;
	f >> t;
	
	for(int i = 0; i < t; i++)
	{
		int n, k;
		f >> n >> k;
		int p = 0, x = n - 1, cnt;
		while(x > 0 && p == 0){
		    cnt = 0;
		for(int j = 2; j <= x; j++){
			if(x % j == 0 && is_prim(j)) cnt++;
			if(cnt == k) {g << x << endl; p = 1; break;}
		}	
			x--;
		}
		if (cnt < k) g << 0 << endl;
	}
	f.close();
	g.close();
}