# include <bits/stdc++.h>
# define int long long
using namespace std;

int n, x, k;

void solve(){
	scanf("%lld%lld%lld", &n, &x, &k);
	int m = x, num = 1, ans = 0;
	int l = x, r = x;
	for (register int i = 1;i <= k;i++){
		l = l*2; r = r*2+1;
		if (l > 2e18) l = 2e18;
		r = min(r, n);
	}
	ans += max(0ll, r-l+1);
  // 先统计它子树内的
  // 再一次一次往上跳
	while (num <= k && m >= 2){
		if (num == k){
			ans++; break;
		}
		int tmp = 1;
      // tmp：兄弟节点
		if (m & 1) tmp = (m / 2) * 2;
		else tmp = (m / 2) * 2 + 1;
		l = tmp, r = tmp;
		for (register int i = 1;i <= k-num-1;i++){
			l = l*2; r = r*2+1; 
			if (l > n) l = n+1;
			if (r > n) r = n;
		}
		ans += max(0ll, r-l+1);
		num++; m /= 2;
	}
	printf("%lld\n", ans);
}

signed main(){
	int T; scanf("%lld", &T);
	while (T--) solve();
	return 0;
}

T 了不用管，样例二的最后一个点错了