#include <fstream>
#include <vector>

using namespace std;

const int N = 1000001;
int v[N] = {0};
vector<int> a[8];

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

void nrdiv()
{
    v[1] = 0;
    for(int i = 2; i < N; i++)
    {
        if(v[i] == 0)
        {
            for(int j = i; j < N; j+=i)
            {
                v[j]++;
            }
        }
    }
    for(int i = 1; i < N; i++)
    {
        a[v[i]].push_back(i);
    }
}

int cb(const int n, const int k)
{
    int r = -1;
    int pas = 1 << 20;
    while(pas != 0)
    {
        if(r+pas < a[k].size() && a[k][r+pas] < n)
        {
            r += pas;
        }
        pas /= 2;
    }
    if (r == -1)
    {
        return 0;
    }
    return a[k][r];
}

int main()
{
    int t, n, k;
    in >> t;
    nrdiv();
    for(int i = 0; i < t; i++)
    {
       in >> n >> k;
       out << cb(n, k) << '\n';
    }
    return 0;
}