#include <cstdio>
#define Nmax 1000005

using namespace std;

int diviz[Nmax+5],dp[Nmax+5][10];

inline void PreCalcul()
{
    int i,j;
    for(i=2;i<=Nmax;i+=2)
        diviz[i]=1;
    for(i=3;i<=Nmax;i+=2)
        if(!diviz[i])
            for(j=i;j<=Nmax;j+=i)
                ++diviz[j];
    for(i=1;i<=Nmax;++i)
        for(j=0;j<=7;++j)
            if(diviz[i]==j)
                dp[i][j]=i;
            else
                dp[i][j]=dp[i-1][j];
}

int main()
{
    int i,x,k,M;
    freopen ("divprim.in","r",stdin);
    freopen ("divprim.out","w",stdout);
    PreCalcul();
    scanf("%d", &M);
    while(M--)
    {
        scanf("%d%d", &x,&k);
        printf("%d\n", dp[x][k]);
    }
    return 0;
}