#include <iostream>
#include <fstream>
#include <algorithm>
#define dMAX 1000002

using namespace std;

unsigned int Q, n, c, result;
unsigned short int k;

struct Element{
    unsigned int number;
    unsigned short int frecv;
} sieve[dMAX];

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

bool Compare(Element e1, Element e2) {
    if (e1.frecv == e2.frecv)
        return e1.number < e2.number;
    return e1.frecv < e2.frecv;
}

void BinarySearch(unsigned int a, unsigned int b) {
    if (a > b) return;
    unsigned c = a + (b - a) / 2;
    if (sieve[c].frecv == k) {
        if (sieve[c].number <= n) {
            result = sieve[c].number;
            BinarySearch(c + 1, b);
        } else
            BinarySearch(a, c - 1);
    } else {
        if (sieve[c].frecv > k) {
            BinarySearch(a, c - 1);
        } else {
            BinarySearch(c + 1, b);
        }
    }
}

int main()
{
    unsigned int i, j;
    fin >> Q;
    sieve[1].frecv = sieve[1].number = 1;
    for (i = 2; i < dMAX; i++) {
        sieve[i].number = i;
        if (sieve[i].frecv == 0) {
            for (j = i + i; j < dMAX; j += i) {
                sieve[j].frecv++;
            }
        }
    }

    sort(sieve, sieve + dMAX, Compare);

    for (i = 1; i <= Q; i++) {
        fin >> n >> k;
        BinarySearch(1, dMAX);
        fout << result << "\n";
        result = 0;
    }
    return 0;
}