#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, pos, lgn;
    for ( int i = 0; i < t; ++i )
    {
        n = Nk[i].first;
        k = Nk[i].second;
        pos = 0;
        int msize = m[k].size() - 1;
        for ( lgn = 1; lgn <= msize; lgn <<= 1 );
        for ( int byte = lgn; byte; byte >>= 1 )
            if ( pos + byte <= msize && m[k][pos + byte] < n )
                pos += byte;


        //if ( n < m[k][l] )
           // --l;
        os << m[k][pos] << '\n';
    }
}