#include <cstdio>
#include <string>
#define MAX 1000000
#define BUF_MAX (1<<18)
using namespace std;
char buf[BUF_MAX];
int poz=BUF_MAX;
inline char GetChar(){
    if(poz==BUF_MAX){
        fread(buf,1,BUF_MAX,stdin);
        poz=0;
    }
    return buf[poz++];
}
inline int GetInt(){
    int x=0;char c;
    do{
        c=GetChar();
    }while(!isdigit(c));
    do{
        x=x*10+c-'0';
        c=GetChar();
    }while(isdigit(c));
    return x;
}
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)
    {
        n=GetInt();
        k=GetInt();
        printf("%d\n",d[k][n]);
    }
    return 0;
}