#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <algorithm>

#define MAX 100000

#define MAX_NUMBER 5045

#define MAX_NUMBER_OF_DIVISORS 8

long long int findBestNumber(long long int upperBound,
                             std::vector<std::vector<long long int>> numberOfDivisors,
                             int i);

std::pair<bool, int>
checkNumberOfDivisors(long long int bound, std::vector<long long int> primes,
                      int maxNumberOfDivisors);

std::vector<long long int> getFirst10000PrimeNumbers() {
    long long int k, i, j;
    std::vector<long long int> primes;
    bool prime[MAX + 1];

    k = 0;
    for (i = 2; i <= MAX; i++) {
        prime[i] = true;
    }
    for (i = 2; i <= MAX; i++) {
        if (prime[i]) {
            k++;
            for (j = i + i; j <= MAX; j = j + i) {
                prime[j] = false;
            }
        }
    }

    for (i = 2; i <= MAX; i++) {
        if (prime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

int main() {
    FILE *input = fopen("divprim.in", "r");
    FILE *output = fopen("divprim.out", "w");
    int numberOfTests;
    int numberOfDivisors;
    long long int upperBound;
    std::vector<std::vector<long long int>> numbersAndDivisors;

    fscanf(input,"%d",&numberOfTests);
    std::vector<long long int> primes = getFirst10000PrimeNumbers();

    for (int i = 0; i < MAX_NUMBER_OF_DIVISORS; i++) {
        std::vector<long long int> temp;
        numbersAndDivisors.push_back(temp);
    }

    for (long long int i = 2; i < MAX_NUMBER; i++) {
        std::pair<bool, int> temp = checkNumberOfDivisors(i, primes, MAX_NUMBER_OF_DIVISORS);
        if (temp.first) {
            int newNumber = temp.second;
            numbersAndDivisors[newNumber].push_back(i);
        }
    }

    for (int i = 0; i < numberOfTests; i++) {
        fscanf(input,"%lld %d", &upperBound, &numberOfDivisors);
        fprintf(output,"%lld\n",
                findBestNumber(upperBound, numbersAndDivisors, numberOfDivisors));
    }

    fclose(input);
    fclose(output);

    return 0;
}

long long int findBestNumber(long long int upperBound,
                             std::vector<std::vector<long long int>> numberOfDivisors,
                             int divisorsNumber) {
    std::vector<long long int> possibleNumbers = numberOfDivisors[divisorsNumber];
    long long int result = possibleNumbers[possibleNumbers.size() - 1];

    if (result < upperBound) {
        return result;
    }

    int index = possibleNumbers.size() - 1;

    while (result > upperBound) {
        result = possibleNumbers[index];
        index--;

        if (index < 0) {
            break;
        }
    }

    if (result > upperBound)
        return 0;

    return result;
}

std::pair<bool, int>
checkNumberOfDivisors(long long int bound, std::vector<long long int> primes,
                      int maxNumberOfDivisors) {
    int numberOfDivisors = 0;

    for (long long int divisor : primes) {
        if (divisor > bound) {
            return std::pair<bool, int> {numberOfDivisors <= maxNumberOfDivisors, numberOfDivisors};
        }

        if (bound % divisor == 0) {
            numberOfDivisors += 1;

            if (numberOfDivisors > maxNumberOfDivisors)
                return std::pair<bool, int> {false, numberOfDivisors};
        }
    }

    return std::pair<bool, int> {true, numberOfDivisors};
}