#include <fstream>

using namespace std;

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

bool isgood(int n, int k){
    int nprim = 0;
    for(int i = 2;i * i <= n;i++){
        if(n % i == 0){
            nprim++;
            if(nprim > k){
                return false;
            }
            while(n % i == 0){
                n /= i;
            }
        }
    }
    if(n > 1){
        nprim++;
        if(nprim > k){
            return false;
        }
    }
    if(nprim < k){
        return false;
    }
    return true;
}

int main()
{
    int n, k, p;
    in >> p;
    for(int i = 0;i < p;i++){
        in >> n >> k;
        while(n > 0){
            if(isgood(n, k)){
                break;
            }
            n--;
        }
        out << n<<"\n";
    }
    return 0;
}