#include <fstream>
#include <vector>

using namespace std;

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

int T,i,j,w[1000005],n,k;
vector<int> L[9];

int main()
{
    fin >> T;

    w[0] = w[1] = 0;
    for (i=2; i<=1000000; i++)
        if (w[i] == 0){
            for (j=2; j<=1000000/i; j++)
                w[i*j]++;
            w[i]=1;
        }


    for (i=0; i<=1000000; i++)
        L[w[i]].push_back(i);
    for (;T--;)
    {
        fin >> n >> k;
        int st = 0;
        int dr = L[k].size()-1;
        int aux = -1;
        while (st <= dr)
        {
            int mid = (st+dr)/2;
            if (L[k][mid] <= n)
            {
                aux = mid;
                st = mid+1;
            }
            else
                dr = mid-1;
        }
        if (aux == -1)
            fout << 0 << "\n";
        else
            fout << L[k][aux] << "\n";
    }
    return 0;
}