const int MAX=15000;
int t,n,num;
int a[2*MAX],b[2*MAX],tmp[2*MAX+5];
int a_len,b_len;
int res;
int add_bit(int *x,int len)
{
    int cntBit=0;
    bool IsFirNumExist=false;
    For(i,1,len+1){
        if(x[i]>=10){
            int yu=x[i]/10;
            x[i]%=10;
            x[i+1]+=yu;
        }
    }
    For(k,1,len+1){
        int i=len-k+1;//highestBit
        if(x[i]!=0&&!IsFirNumExist){
            IsFirNumExist=true;
            cntBit=i;
        }
    }
    return cntBit;
}
void fac()
{
    For(i,1,a_len+1){
        For(j,1,b_len+1){
            tmp[i+j-1]+=a[i]*b[j];
        }
    }
    a_len=add_bit(tmp,a_len+b_len);

    For(i,1,a_len+b_len+1){
        a[i]=tmp[i];
    }
    memset(tmp,0,2*MAX);
}

void show()
{
    For(i,1,a_len+1){
        if(a[a_len+1-i]==num)   res++;
//        cout<<a[a_len+1-i];
    }
    cout<<res<<endl;
    res=0;
//    cout<<endl;
}

void input()
{
    r(t);
    For(index,0,t){
        rr(n,num);
        a[1]=1;
        a_len=b_len=1;
        For(i,1,n+1){
            memset(b,0,2*MAX);
            b[1]=i;
            b_len=i/10+1;
            if(b_len>1) add_bit(b,b_len);
            fac();
        }
        show();
    }
}