#include <fstream>
#include <vector>
#define VAL 1000005

using namespace std;

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

int T, N, K, i, j;
int nr[VAL];
bool ok[VAL];
vector <int> v[15];

void Sieve()
{
    for (i=2; i<VAL; i++)
    {
        if (ok[i]==false)
        {
            nr[i]++;
            for (j=2*i; j<VAL; j+=i)
            {
                ok[j]=true;
                nr[j]++;
            }
        }
    }
}

int Binary_Search()
{
    int be=0, en=v[K].size()-1;
    int mid, ans=0;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (v[K][mid]<=N)
        {
            ans=v[K][mid];
            be=mid+1;
        }
        else
          en=mid-1;
    }
    return ans;
}

int main()
{
    fin >> T;
    Sieve();
    for (i=1; i<VAL; i++)
      v[nr[i]].push_back(i);
    for (i=1; i<=T; i++)
    {
        fin >> N >> K;
        fout << Binary_Search() << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}