#include <stdio.h>

#define Nmax 1000100
#define Kmax 8

int sol[Nmax][Kmax],ciur[Nmax],n,k,t;

void gen()
{
    int i,j;
    for(i=2;i<Nmax;++i)
        if(!ciur[i])
            for(j=i+i;j<Nmax;j=j+i)
                ++ciur[j];
    sol[1][0]=1;
    for(i=2;i<=1000000;++i)
        for(k=1;k<=7;++k)
            {
                sol[i][k]=sol[i-1][k];
                if(ciur[i]==k)
                    sol[i][k]=i;
            }
}

int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    gen();
    while(t--)
        {
            scanf("%d%d",&n,&k);
            if(sol[n][k])
                printf("%d\n",sol[n][k]);
            else
                printf("0\n");            
        }
    return 0;   
}