样例全过，WA2个点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
#include<list>
#include<set>
#include<queue>
#include<map>
#include<stack>
#include<ctime>
#include<random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
const ll MAXN=1e6;
const ll inf=0x3f3f3f3f;
const ll infll=0x3f3f3f3f3f3f3f3f;
ll n,x,k;
ll calc(i128 u,ll dis){
    i128 v=u;
    for(ll i=1;i<=dis;i++){
        u<<=1;
        if(u>n){
            return 0;
        }
    }
    for(ll i=1;i<=dis;i++){
        v<<=1;
        v++;
    }
    if(v>n){
        return n-u+1;
    }
    else{
        return v-u+1;
    }
}
void solve(){
    cin>>n>>x>>k;
    ll ans=calc(x,k);
    while(k&&x!=1){
        ll fa=(x>>1);
        if(x==fa*2+1){
            ans+=calc(fa*2,k-2);
        }
        else{
            ans+=calc(fa*2+1,k-2);
        }
        x=fa;
        k--;
    }
    cout<<ans<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}