E

#include <bits/stdc++.h>

using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)

int main()
{
    _test
    {
        ll int n, k, x;
        cin>>n>>x>>k;

        if(k == 0)
        {
            cout<<1<<"\n";
            continue;
        }

        unordered_map<ll int, ll int> nxt;
        ll int tmp = x;
        while(x > 0)
        {
            nxt[x/2] = x;
            x /= 2;
        }

        x = tmp;

        ll int ans = 0;
        int dep = 0;

        function<ll int(ll int, ll int)> func = [&](ll int u, ll int nodes)
        {
            vector<ll int> lvlNodes(75);
            lvlNodes[0] = 1;
            ll int tot = 1;
            ll int curr = 2;
            int i = 1;

            while(tot+curr <= nodes)
            {
                lvlNodes[i++] = curr;
                tot += curr;
                curr *= 2;
            }

            ll int rem = (nodes - tot);

            lvlNodes[i] = rem;

            ll int left = (tot-1)/2;
            ll int right = (tot-1)/2;

            if(rem)
            {
                if(rem <= lvlNodes[i-1])
                    left += rem;
                else
                {
                    left += lvlNodes[i-1];
                    right += rem - lvlNodes[i-1];
                }
            }

            ll int tmp = 0;

            if(u != x)
            {
                if(nxt[u]==2*u)         tmp = func(2*u, left);
                if(nxt[u]==2*u+1)       tmp = func(2*u+1, right);
            }

            if(dep<=k && k-dep>=0 && k-dep<70)
            {
                if(dep == k)        ans += lvlNodes[k-dep];
                else                ans += lvlNodes[k-dep] - tmp;
            }

            dep++;

            tmp = 0;
            if(k-dep-1 >= 0 && k-dep-1<70)        tmp = lvlNodes[k-dep-1];

            return tmp;
        };

        func(1, n);

        cout<<ans<<"\n";
    }
}