#include <fstream>

using namespace std;

int v[8][1000001];
int nrd[1000001];

ifstream in ("divprim.in");
ofstream out ("divprim.out");

int main()
{
    long long i,j;
    for (i=2; i<=1000000; i++)
        if (!nrd[i])
            for (j=i; j<=1000000; j+=i)
                nrd[j]++;
    int t,n,k;
    for (i=1; i<=1000000; i++)
    {
        for (j=1; j<=7; j++)
            v[j][i]=v[j][i-1];
        if (nrd[i]<=7)
            v[nrd[i]][i]=i;
    }
    in>>t;
    for (i=1;i<=t;i++)
    {
      in>>n>>k;
      out<<v[k][n]<<'\n';
    }
    return 0;
}