#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,k,n,a[1000005],s[1000005][11],i,j;
int main()
{
    fin>>t;
    s[1][0]=0;
    for(i=2;i<1000005;i++)
    {
        if(!a[i])
            for(j=i;j<1000005;j+=i)
                ++a[j];
        for(j=0;j<=7;j++)
            s[i][j]=s[i-1][j];
        if(a[i]<=7)
            s[i][a[i]]=i;
    }
    for(i=1;i<=t;i++)
    {
        fin>>n>>k;
        fout<<s[n][k]<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}