#include<stdio.h>
#define maxim 1000000
int n,a,b,i,j;
int div[1000001];
int sol[1000001][8];
int main()
{
        freopen("divprim.in","r",stdin);
        freopen("divprim.out","w",stdout);
        scanf("%d",&n);
        div[i]=1;
        for(i=2;i<=maxim;++i)
            if(div[i]==0)
                for(j=i;j<=maxim;j+=i)
                    ++div[j];
        for(i=2;i<=maxim;++i)
            {
                for(j=1;j<=7;++j)
                    sol[i][j]=sol[i-1][j];
                sol[i][div[i]]=i;
            }
        for(i=1;i<=n;++i)
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",sol[a][b]);
            }
        return 0;
}