#include <fstream>

using namespace std;

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

#define N 100005
int c[N + 5];
void ciur()
{
    c[0] = c[1] = 0;
    c[2] = 1;
    for(int i = 4; i <= N; i += 2)
        c[i] = 0;
    for(int i = 3; i <= N; i += 2)
        c[i] = 1;
    for(int i = 3; i * i <= N; i += 2)
        if(c[i])
            for(int j = 3 * i; j <= N; j += 2 * i)
                c[j] = 0;
}

int nrdiv[N];
void NrDiv()
{
    for(int i = 1; i <= N; i++)
        if(c[i])
            for(int j = i; j <= N; j += i)
                nrdiv[j]++;
}
int T, n, k;
int main()
{
    fin >> T;
    ciur();
    NrDiv();
    for(int i = 1; i <= T; i++)
    {
        fin >> n >> k;
        while(nrdiv[n] != k && n > 0)
            n--;
        fout << n << "\n";
    }
    return 0;
}