#include <fstream>
#include <vector>

using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
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;
    f>>t;
    ciur();
    for(int i=1;i<=t;++i)
    {
        int a,b;
        f>>a>>b;
        int st=0,dr=v[b].size()-1,sol=0;
        while(st<=dr)
        {
            int mid=st+(dr-st)/2;
            if(v[b][mid]<=a)
            {
                st=mid+1;
                sol=v[b][mid];
            }
            else dr=mid-1;
        }
        g<<sol<<'\n';
    }
    return 0;
}