#include <fstream>
#include <vector>
using namespace std;

ifstream is("divprim.in");
ofstream os("divprim.out");

vector<vector<int> > m;
vector<int> nrdiv;
vector<pair<int, int> > Nk;
int t;
int nmax, kmax;

void Ciur(int x);
void Read();
void Solve();


int main()
{
    Read();
    Ciur(nmax);
    Solve();

    is.close();
    os.close();
    return 0;
}

void Ciur(int x)
{
    for ( int i = 2; i <= x; i += 2 )
        ++nrdiv[i];
    for ( int i = 3; i <= x; i += 2 )
        if ( !nrdiv[i] )
        {
            for ( int j = i; j <= x; j += i )
                ++nrdiv[j];
        }
}

void Read()
{
    is >> t;
    m = vector<vector<int> >(8);
    int n, k;
    for ( int i = 1; i <= t; ++i )
    {
        is >> n >> k;
        Nk.push_back({n, k});
        nmax = max(nmax, n);
        kmax = max(kmax, k);
    }
    nrdiv = vector<int>(nmax + 15);
}

void Solve()
{
    for ( int i = 0; i <= kmax; ++i )
        m[i].push_back(0);
    for ( int i = 1; i <= nmax; ++i )
        if ( nrdiv[i] < 8 )
            m[nrdiv[i]].push_back(i);

    int n, k;
    for ( int i = 0; i < t; ++i )
    {
        n = Nk[i].first;
        k = Nk[i].second;
        int l = 0, r = m[k].size() - 1;
        int mij;
        while ( l != r )
        {
            mij = (l + r + 1) / 2;
            if ( n >= m[k][mij] )
                l = mij;
            else
                r = mij - 1;
        }
        if ( n < m[k][l] )
            --l;
        os << m[k][l] << '\n';
    }
}