#include <cstdio>
#include <string>
#define MAX 1000000
using namespace std;
int d[8][MAX+1],v[MAX+1],n,k,t; //d de i de j - cel mai mare elemenet cu i divizori primi mai mic sau egal decat j
void usu()
{
    for(int i=2;i<=MAX;++i) //ciur modificat astfel incat contorizam pt fiecare cati divizori primi are
    {
        if(!v[i])
        {
            for(int j=i+i;j<=MAX;j=j+i) ++v[j];
            v[i]=1;
        }
    }
}
void precalculare()
{
    for(int i=1;i<=7;++i) //maxim 7 divizori primi, ne spune in enunt
    {
        for(int j=1;j<=MAX;++j)
        {
            if(v[j]==i) d[i][j]=j; //daca elementul are i div primi --- avem elementul maximal cu i divizori pana la j
            else d[i][j]=d[i][j-1]; //daca nu descoperim alt element cu i divizori, il consideram cel mai mare pe cel mai mare mai mic decat j
        }
    }
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    usu();
    scanf("%d",&t);
    precalculare();
    for(int i=1;i<=t;++i)
    {
        scanf("%d%d",&n,&k);
        printf("%d\n",d[k][n]);
    }
    return 0;
}