#include<stdio.h>
int p[1000001],x[1000001],l,i,j,n,r[1000001],s[1000001][8],t,k,a;
int main()
{
    freopen("divprim.in","r",stdin),freopen("divprim.out","w",stdout),x[++l]=2;
    for(i=1;((i*i)<<1)+(i<<1)<1000001;++i)
        if((p[i>>3]&(1<<(i&7)))==0)
            for(j=((i*i)<<1)+(i<<1);(j<<1)+1<1000001;j+=(i<<1)+1)
                p[j>>3]|=(1<<(j&7));
    for(i=1;2*i+1<1000001;++i)
        if((p[i>>3]&(1<<(i&7)))==0)
            x[++l]=2*i+1;
    for(i=1;i<=l;++i)
        for(j=x[i];j<1000001;j+=x[i])
            ++r[j];
    for(i=1;i<1000001;++i) {
        for(j=0;j<8;++j)
            s[i][j]=s[i-1][j];
        s[i][r[i]]=i;
    }
    scanf("%d",&t);
    while(t--)
        scanf("%d%d",&n,&k),printf("%d\n",s[n][k]);
    return 0;
}