#include <fstream>
#include <bitset>

using namespace std;

bitset<1000001> p;
int prime[100000];
ifstream in("divprim.in");
ofstream out("divprim.out");
int i, j, rez, k, n, t, k2;
bool gasit = false;
int main()
{
    for(i = 2; i <= 1000; i++) {
        if(p.test(i) == 0) for(j = i*i; j <= 1000000; j=j+i) p.set(j, 1);
    }
    j = 0;
    p.set(1, 1);
    for(i = 2; i <= 1000000; i++) if(p.test(i) == 0) prime[++j] = i;

    in >> t;

    for(i = 1; i <= t; i++) {
        in >> n >> k;
        gasit = false;
        if(n == 1) out << "1\n";
        else {
            while(gasit == false && n != 0) {
                if(p.test(n) == 0) { n--; continue; }
                k2 = k;
                j = 1;
                while(prime[j] <= n/2) {
                    if(n%prime[j] == 0) k2--;
                    j++;
                }
                if(k2 == 0) out << n << "\n", gasit = true;
                else n--;
            }
            if(gasit == false) out << "0\n";
        }
    }
    return 0;
}