#include<bits/stdc++.h>

using namespace std;

#define int long long

int xx[],yy[],cnt1,cnt2;

int dp[][][];

inline int work(int a,int b,int s,int c){

    int i,j,k,d=max(max(a-,b),(int)log2(s)+1ll),x,y,z,g;

    for(i=;i<=d;i++)

      for(j=;j<=c;j++)

        dp[i][j][]=dp[i][j][]=;

    i=;

    for(x=;x<=;x++)

      for(y=;y<=;y++){

          k=(x+y)>>,z=(x+y)&;

          if(i==b-&&!y)continue;

          if(z!=(s&))continue;

          if(i>b-&&y)continue;

          if(i>a-&&x)continue;

          dp[i][x+y][k]++;

      }

    for(i=;i<=d;i++)

      for(j=;j<=c;j++)

        for(g=;g<=;g++)

          if(dp[i-][j][g])

            for(x=;x<=;x++)

              for(y=;y<=;y++){

                k=(x+y+g)>>,z=(x+y+g)&;

                  if(i==b-&&!y)continue;

                  if(z!=((s&(1ll<<i))?:))continue;

                  if(i>b-&&y)continue;

                  if(i>a-&&x)continue;

                  dp[i][j+x+y][k]+=dp[i-][j][g];

              }

    return dp[d][c][];

}

inline int sum(int x){

    int res=x<<;

    while(x)res-=(x&1ll),x>>=;

    return res;

}

signed main(){

    int x,y,z,d,c,i,j,k,t,x2,y2,s,a,b;

    scanf("%lld",&t);

    while(t--){

      scanf("%lld%lld%lld%lld",&d,&x,&y,&c);

      cnt1=cnt2=;

      x2=x,y2=y;

      while(x2)xx[++cnt1]=(x2&),x2>>=;

      while(y2)yy[++cnt2]=(y2&),y2>>=;

      reverse(xx+,xx+cnt1+);

      reverse(yy+,yy+cnt2+);

      z=;

      for(i=;i<=min(cnt1,cnt2);i++)

        if(xx[i]==yy[i])z=(z<<)+xx[i];

          else break;

      s=sum(x)+sum(y)-sum(z)-sum(z>>);

      if(c==){

          printf("%lld\n",s);

          continue;

      }

      int Ans=;

      for(a=;a<d;a++)

        for(b=;b<d;b++){

          int v=(1ll<<(a+))+(1ll<<(b+))-;

          z=s/v;

          if(!z)continue;

          if((int)log2(z)+max(a,b)+>d)continue;

          k=s-z*v;

          for(i=;i<=a+b;i++)

            if((i+k)%==)Ans+=work(a,b,(i+k)>>,i);

        }

      printf("%lld\n",Ans-);

    }

    return ;

}