#include <fstream>
#include <vector>

using namespace std;

#define Nmax 1000000

vector<int> v[9];

int ciur[Nmax];

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

    int t, i, j, n, x, l, r, mid, sol, val;

    fin >> t;

    ciur[0] = 1;
    ciur[1] = 1;

    for(i = 2; i * i <= Nmax; i++)
    {
        if(ciur[i] == 0)
        {
            for(j = i * 2; j <= Nmax; j += i)
            {
                ciur[j]++;
            }
        }
    }

    for(i = 2; i <= Nmax; i++)
    {
        v[ciur[i]].push_back(i);
    }

    for(i = 1; i <= t; i++)
    {
        fin >> n >> x;
        if(x < 8 && n < v[x][0])
        {
            sol = 0;
        }
        else
        {
            l = 0;
            r = v[x].size() - 1;
            while(l <= r)
            {
                mid = (l + r) / 2;
                val = v[x][mid];
                if(n >= val)
                {
                    sol = val;
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
        }
        fout << sol << '\n';
    }
    return 0;
}