#include <fstream>

using namespace std;

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

int v[8][1000001], c[1000001];

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