目测时间复杂度 $\mathcal{O(\log^2 n)}$。但是 T 乐

#include <bits/stdc++.h>

#pragma GCC optimize(2)
 
using namespace std;

// int &read(int &r){r=0;bool w=0;char ch=getchar();while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();return r=w?-r:r;}
long long &read(long long &r){r=0;bool w=0;char ch=getchar();while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();return r=w?-r:r;}
double &read(double& x) {x = 0;double t = 0;short f = 1, s = 0;char c = getchar();while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();if (c == '.') c = getchar();else { x *= f; return x; }while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();while (s--) t /= 10.0;x = (x + t) * f;return x;}
long double &read(long double& x) {x = 0;long double t = 0;short f = 1, s = 0;char c = getchar();while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();if (c == '.') c = getchar();else { x *= f; return x; }while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();while (s--) t /= 10.0;x = (x + t) * f;return x;}
char &read(char& c) {c = getchar();while (c == ' ' || c == '\n' || c == '\r') c = getchar();return c;}
char* &read(char* str) {int len = 0;char c = getchar();while (c == ' ' || c == '\n' || c == '\r') c = getchar();while (c != ' ' && c != '\n' && c != '\r') str[len++] = c, c = getchar();str[len] = '\0';return str;}
string&read(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return str;}
__float128&read(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return x;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return x;}
template<typename T1,typename... T2>
void read(T1 &x,T2& ...y){read(x);read(y...);}
 
typedef long long ll;
#define S(T, Q) if (Q) T = 1; else read(T);while(T--)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back

#define int long long 

int power(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * a)
		if (b & 1) res = res * a;
	return res;
}

int T;
int n, X, K;
int ans = 0;
int Power2[60];

bool mul(int &x, int t) {
	int res = 0;
	while (t) {
		if (t & 1) {
			res = res + x;
			if (res > n) return true;
		}
		x = x + x;
		t >>= 1;
		if (x > n && t) return true;
	}
	x = res;
	return false;
}

void dfs(int x, int opt, int k) { // opt:0/1/2
	if (!k) {
		++ans;
		return;
	}
	if (x > n) return;
	if (k <= 0ll) return;
	// if (n == 10 && K == 3) {
	// 	cout << x << endl;
	// }
	if (opt == 2) {
		if (X == x) {
			if (x % 2ll) dfs(x / 2ll, 0ll, k - 1ll);
			else dfs(x / 2ll, 1ll, k - 1ll);
		}
		if (k > 60ll) return;
		if (mul(x, Power2[k])) return;

		if (x >= n) return;
		int l = x, r = x + Power2[k] - 1ll;
		while (l < r) {
			int mid = (l + r + 1ll) >> 1ll;
			if (n >= mid) l = mid;
			else r = mid - 1ll;
		}
		// if (n == 10 && K == 3) {
		// 	cout << x << ' ' << l << endl;
		// }
		ans += r - x + 1ll;
		return;
	} else {
		if (opt == 0) dfs(x * 2ll, 2ll, k - 1ll);
		else dfs(x * 2ll + 1ll, 2ll, k - 1ll);
		if (x == 1) return;
		if (x % 2) dfs(x / 2ll, 0ll, k - 1ll);
		else dfs(x / 2ll, 1ll, k - 1ll);
	}
}

signed main() {
	for (int i = 0ll; i <= 60ll; ++i) Power2[i] = power(2ll, i);
    S(T, 0) {
    	ans = 0ll;
    	read(n, X, K);
    	if (K == 0ll) {
    		puts("1");
    		continue;
    	}
    	dfs(X, 2ll, K);
    	printf("%lld\n", ans);
    }
    return 0;
}