首先我们只考虑x子树中的答案，非常明显，一定是一个连续的区间，那么我们只需要找到两个端点即可，左端点一直往左走即可，但是右端点要注意，如果走不了，如果左端点存在，说明n就是我们的右端点。
处理完子树之后往上跳即可，因为树高只有60
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc ( iint(2)*x )
#define rc ( iint(2)*x+iint(1) )
using namespace std;
typedef double db;
typedef long long ll;
typedef __int128 iint;
const int N =1e6+6;
const ll mo=998244353;
const ll inf=1ll<<60;
ll nn,xx,kk;
iint n,x,k,l,r,lx;
void dg(iint x,iint k,int op){
if (!k) {
l=min(l,x);
r=max(r,x);
return;
}
if (!op) {
if (lc<=n) dg(lc,k-1,op);
}
else{
if (rc<=n) dg(rc,k-1,op);
else r=n;
}
}
void solve(){
ll ans=0;
n=nn; x=xx; k=kk;
if (!k) {
printf("%d\n",1);
return;
}
l=inf; r=0;
dg(x,k,0);
dg(x,k,1);
if (l<=r) ans+=r-l+(iint)1;
lx=x;
x/=(iint)2; k--;
while (x) {
if (!k) {
ans++; break;
}
l=inf; r=0;
if (lc!=lx && lc<=n) dg(lc,k-1,0),dg(lc,k-1,1);
if (rc!=lx && rc<=n) dg(rc,k-1,0),dg(rc,k-1,1);
if (l<=r) ans+=r-l+1ll;
k--;
lx=x;
x/=2ll;
}
printf("%lld\n",ans);
}
int main()
{
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
// T=1;
while (T--){
scanf("%lld %lld %lld",&nn,&xx,&kk);
solve();
}
return 0;
}