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

#define MAX 1299721

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

bool
checkNumberOfDivisors(long long int bound, std::vector<long long int> vector,
                      int divisors);

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;

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

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

    fclose(input);
    fclose(output);

    return 0;
}

long long int findBestNumber(long long int upperBound, int numberOfDivisors,
                             std::vector<long long int> primes) {
    while (upperBound >= 1) {
        bool hasNumberOfDivisors = checkNumberOfDivisors(upperBound, primes, numberOfDivisors);
        if (hasNumberOfDivisors) {
            break;
        }
        upperBound--;
    }
    return upperBound;
}

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

    for (long long int divisor : vector) {
        if (divisor > bound) {
            return (numberOfDivisors == divisors);
        }

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

            if (numberOfDivisors > divisors)
                return false;
        }
    }
    return true;
}