#include<cstdio>
using namespace std;
const int NMAX = 1000005;
int F[NMAX],i,j,DP[NMAX][8],T;
// DP[i][j] = cel mai mare numar mai mic decat i cu j divizori primi
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    for(i=2;i<NMAX;i++)
        if(!F[i])
            for(j=i;j<NMAX;j+=i) F[j]++;
    for(i=2;i<NMAX;i++)
    {
        for(j=1;j<=7;j++)
            DP[i][j]=DP[i-1][j];
        DP[i][F[i]]=i;
    }
    scanf("%d",&T);
    for(;T;T--)
    {
        scanf("%d%d",&i,&j);
        printf("%d\n",DP[i][j]);
    }
    return 0;
}