#include <fstream>
#include <vector>
using namespace std;
ofstream out ("divprim.out");
ifstream in ("divprim.in");
short prim[1000001];
vector <int> v[20];
void ciur ()
{
    for (int i=2;i<=1000000;++i)
    {
        if (!prim[i])
        {
            prim[i]++;
            for (int j=i+i;j<=1000000;j+=i)
                prim[j]++;
        }
    }
    for (int i = 1; i<= 1000000;++i)
            v[prim[i]].push_back(i);
    return;
}
int main()
{
    int t;
    in>>t;
    ciur();
    for (int i = 1;i<=t;++i)
    {
        int a,b;
        in>>a>>b;
        int st = 0,dr=v[b].size()-1,save=0;
        while (st<=dr)
        {
            int mid = st + (dr - st)/2;
            if (v[b][mid]<=a)
            {
                st=mid+1;
                save=v[b][mid];
            }
            else
                dr=mid-1;
        }
        out<<save<<'\n';
    }
    return 0;
}