#include <fstream>
#include <vector>

using namespace std;

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

vector <int> a[8];

const int N = 1000001, L = 19;
int nrd[N];

int CautBin(int nr, int i)
{
    int r=0, pas=1<<L;
    while(pas!=0)
    {
        if(r+pas<a[i].size() && a[i][r+pas]<=nr) r+=pas;
        pas/=2;
    }
    return a[i][r];
}

int main()
{
    for(int i=2; i<=N; i++)
    {
        if(nrd[i]==0)
        {
            for(int j=i; j<N; j+=i) nrd[j]++;
        }
    }
    for(int i=1; i<8; i++) a[i].push_back(0);
    for(int i=1; i<=N; i++) a[nrd[i]].push_back(i);

    int t;
    in >> t;
    for(int i=1; i<=t; i++)
    {
        int nr, nrdiv;
        in >> nr >> nrdiv;
        out << CautBin(nr, nrdiv) << '\n';
    }
    return 0;
}