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

#define MAX 1000000
#define MAX_NUMBER_OF_DIVISORS 8

int main() {
    FILE *input = fopen("divprim.in", "r");
    FILE *output = fopen("divprim.out", "w");
    int numberOfTests;
    int numberOfDivisors;
    int upperBound;

    int primes[MAX + 1];
    primes[0] = 0;
    primes[1] = 0;
    for (int i = 2; i <= MAX; i++)
        if (primes[i] == 0)
            for (int j = i; j <= MAX; j += i)
                primes[j]++;

    int solution[MAX + 1][MAX_NUMBER_OF_DIVISORS + 1];
    solution[1][0] = 1;

    for (int i = 2; i <= MAX; i++) {
        for (int j = 0; j <= 7; j++) {
            solution[i][j] = solution[i - 1][j];
        }
        solution[i][primes[i]] = i;
    }

    fscanf(input, "%d", &numberOfTests);
    for (int i = 0; i < numberOfTests; i++) {
        fscanf(input, "%d %d", &upperBound, &numberOfDivisors);
        fprintf(output, "%d", solution[upperBound][numberOfDivisors]);
    }

    fclose(input);
    fclose(output);

    return 0;
}