#include <iostream>
#define int long long
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int lg = 59;
int T, n, x, k, fl;
inline int down(int x, int k) {
	int r = x,  ans = 1;
//	if (fl)	cout << x << ' ' << k << ' ';
	for (int i = 1; i <= lg; ++i) {
		if (r * 2 + 1 <= n)	r = r * 2 + 1;
		else if (r * 2 <= n)	r = r * 2;
		else	break;
	}
	for (int i = 1; i <= k; ++i)
		if (x * 2 + 1 <= r)	ans <<= 1, x = x * 2 + 1;
		else {
			ans = ans * 2 - 1;
			if (n > r || i != k)	ans = 0;//, cout << "INTO ";
			break;
		}
//	if (fl)	cout << ans << '\n';
	return ans;
}
// 0 : fa
// 1 : lt
// 2 : rt
int dfs(int u, int k, int op) {
	if (u > n || u < 1)	return 0;
//	if (fl)	cout << "DFS: " << u << ' ' << k << ' ' << op << '\n';
	if (k == 0)	return 1;
	if (op == 0)	return down(u, k);
	if (op == 1)	return dfs(u * 2 + 1, k - 1, 0) + dfs(u / 2, k - 1, (u & 1ll ? 2 : 1));
	if (op == 2)	return dfs(u * 2, k - 1, 0) + dfs(u / 2, k - 1, (u & 1ll ? 2 : 1));
	return dfs(u * 2, k - 1, 0) + dfs(u * 2 + 1, k - 1, 0) + dfs(u / 2, k - 1, (u & 1ll ? 2 : 1));
}
signed main() {
	cin >> T;
	while (T--) {
		cin >> n >> x >> k;
//		if (x == 2 && k == 3)	fl = 1;
		cout << dfs(x, k, 3) << '\n';
//		fl = 0;
	}
	return 0;
}