#include <fstream>

using namespace std;

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

#define N 1000005
bool 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;
        bool ok = 0;
        for(int j = n; j >= 0; j--)
            if(nrdiv[j] == k)
            {
                fout << j << "\n";
                ok = 1;
                break;
            }
        if(!ok)
            fout << 0 << "\n";
    }
    return 0;
}