#include<bits/stdc++.h>

using namespace std;
const int mo=1000000007;
long long s;
int n;
int H1,H2;
long long ned;
long long f[55][102][2];
long long sav[55][102][2];
pair<int,int> sv[55][102][2];
long long calc(int now,int cnt,int jw){
    if(cnt<0)return 0;
    if((1ll<<now)>ned)return (cnt==0);
    if(ned/(1ll<<now)<cnt)return 0;
    if(sav[now][cnt][jw]==ned&&sv[now][cnt][jw]==make_pair(H1,H2))return f[now][cnt][jw];
    long long ans=0;sav[now][cnt][jw]=ned;sv[now][cnt][jw]=make_pair(H1,H2);
    int hav=(now<=H1)+(now<=H2);
    bool pd=(1ll<<now)&ned;
    if(jw==pd){
        ans+=calc(now+1,cnt,0);
        if(hav==2)ans+=calc(now+1,cnt-2,1);
    }
    else ans+=calc(now+1,cnt-1,jw)*hav;
    return f[now][cnt][jw]=ans;
}
void Solve(long long s){
    long long ans=0;
    for(int i=1;(1ll<<i)-1<=s;i++){
        long long x=s%((1ll<<i)-1),y=s/((1ll<<i)-1);
        if(__lg(y)+i>n)continue;
        for(int j=i-1;j>=1;j--)
            if(x>=(1ll<<j)-1)x-=(1ll<<j)-1;
        if(x==0)ans++;
    }
    for(int h1=1;((1ll<<h1)-1)*2+1<=s;h1++){
        for(int h2=1;((1ll<<h1)-1)*2+1+3*((1ll<<h2)-1)<=s;h2++){
            long long x=(s-((1ll<<h2)-1))%(((1ll<<h1)+(1ll<<h2)-2)*2+1);
            long long y=(s-((1ll<<h2)-1))/(((1ll<<h1)+(1ll<<h2)-2)*2+1);
            if(__lg(y)+max(h1,h2)+1>n)continue;
            if(!x){ans++;continue;}
            H1=h1-1;H2=h2-1;
            for(int i=1;i<=h1+h2-2;i++)
                if(!((x+i)&1)){ned=x+i;ans+=calc(1,i,0);}
        }
    }
    printf("%lld\n",ans-1);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int op;
        long long a,b;
        scanf("%d%lld%lld%d",&n,&a,&b,&op);
        long long sum=a+b;
        while(a!=b){
            if(a<b)swap(a,b);
            sum+=a/2;a/=2;
        }
        sum-=a;
        if(op==1)printf("%lld\n",sum);
        else Solve(sum);
    }
    return 0;
}