#include <fstream>
#inlcude <vector>
#define nmax 1000003
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
vector <int> numere[9];
int ciur[1000004],x,y,i,j;

int main()
{
    for (i=2;i<=nmax;i++)
    {
        if (ciur[i]==0)
        {
            ciur[i]=1;
            for (j=2*i;j<=nmax;j+=i)
             ciur[j]++;
        }
    }
    for(i=1;i<=8;i++)
      numere[i].push_back(0);
    for(i=1;i<=nmax;i++)
      nd[ciur[i]].push_back(i);
    f>>n;
    for(i=1;i<=n;i++)
    {
    f>>x>>y;
    g<<*(lower_bound(numere[y].begin(),numere[y].end(),x)-1)<<'\n';
    }
    return 0;
}