ABC321E WA

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    ll t, n, x, k;
    cin >> t;
    while (t--) {
        cin >> n >> x >> k;
        dbg(n, x, k);
        auto lsb = [](ll r, ll d) -> ll { return r << d; };
        auto rsb = [](ll r, ll d) -> ll {
            if (std::__lg(r) + d >= 63)
                return LLONG_MAX;
            return (r << d) + (1ll << d) - 1ll;
        };
        function<ll(ll, ll)> get_child_cnt = [n, &get_child_cnt, &lsb, &rsb](ll root, ll dep) -> ll {
            if (dep == 0)
                return ll(root <= n);
            if (root > n || root == 0)
                return 0ll;
            ll ls = root * 2, rs = root * 2 + 1;
            ll cnt = 0;

            if (rsb(ls, dep - 1) <= n) {
                cnt += 1ll << (dep - 1);
                if (rsb(rs, dep - 1) <= n)
                    cnt += 1ll << (dep - 1);
                else
                    cnt += get_child_cnt(rs, dep - 1);
            } else
                cnt += get_child_cnt(ls, dep - 1);
            return cnt;
        };

        ll ans = get_child_cnt(x, k);
        dbg(x, k, ans);
        ll os = x ^ 1, dep = k - 2;
        while (dep >= 0 && os) {
            ans += get_child_cnt(os, dep);
            os = ((os / 2) ^ 1), dep -= 1;
        }
        // ans += ll((x >> k) != 0) - ll(k == 0);
        cout << ans << endl;
    }
    return 0;
};