#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

// Funcție pentru a genera numere prime folosind Ciurul lui Eratostene
vector<int> sieve(int max) {
    vector<bool> is_prime(max + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max; j += i) {
                is_prime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= max; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

// Funcție pentru a număra numărul de divizori primi ai unui număr
int count_prime_divisors(int num, const vector<int>& primes) {
    int count = 0;
    for (int prime : primes) {
        if (prime * prime > num) break;
        if (num % prime == 0) {
            while (num % prime == 0) {
                num /= prime;
            }
            count++;
        }
    }
    if (num > 1) count++;
    return count;
}

int main() {
    ifstream inFile("divprim.in");
    ofstream outFile("divprim.out");

    int T;
    inFile >> T;

    const int MAX_N = 1000000;
    vector<int> primes = sieve(MAX_N);

    while (T--) {
        int N, K;
        inFile >> N >> K;

        int result = 0;
        for (int i = N; i >= 1; --i) {
            if (count_prime_divisors(i, primes) == K) {
                result = i;
                break;
            }
        }

        outFile << result << endl;
    }

    inFile.close();
    outFile.close();

    return 0;
}