#include <fstream>
using namespace std;
ifstream in ("divprim.in");
ofstream out ("divprim.out");
short ciur [1000001];
int rasp[8][1000001];
void ciur1 ()
{
    ciur[1]=0;
    for (int i = 2;i <=19; ++i)
    {
        if (!ciur[i])
        {
            ciur[i]++;
            for (int j=i*i;j<=1000000;j+=i)
                ciur[j]++;
        }
    }
    for (int i = 1;i <= 1000000; ++ i)
        for (int j = 0;j <= 7; ++ j)
            if (ciur[i] == j)
                rasp[j][i] = i;
            else
                rasp[j][i] = rasp[j][i-1];
    return;
}
int main ()
{
    int n;
    in>>n;
    ciur1();
    for (int i = 1;i<=n;++i)
    {
        int a,b;
        in>>a>>b;
        out<<rasp[b][a]<<'\n';
    }
    return 0 ;
}