#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
short int s[1000001];
unsigned int i,ss[1000001][8],x,y,n;
int ciur()
{
    int i=0,j=0;
    s[1]=1;
    s[0]=1;
    for(i=2;i<=1000001;i++)
    {
        if(s[i]==0)
            for(j=i;j<=1000001;j=j+i)
                s[j]++;
        for(j=0;j<=7;j++)
            ss[i][j]=ss[i-1][j];
        if(s[i]<=7)
            ss[i][s[i]]=i;
    }
    return 0;
}
int main()
{
    fin>>n;
    ciur();
    for(i=1;i<=n;i++)
    {
        fin>>x>>y;
        fout<<ss[x][y]<<'\n';
    }
    return 0;
}