#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]);
}