#include <fstream>

using namespace std;

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

int t,n,k,i,j;
int c[1000001];
int rez[1000001][8];

int main()
{
    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++)
            if (c[i]==j && i>rez[i-1][j])
                rez[i][j]=i;
            else
                rez[i][j]=rez[i-1][j];

    f>>t;
    while (t--)
    {
        f>>n>>k;
        g<<rez[n][k]<<"\n";
    }

    return 0;
}