第一个样例能过，第二个过不去QAQ

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

typedef long long LL;

LL n, depn;

LL power(LL a, LL b)
{
    if (b < 0) return 0;
    LL res = 1;
    while (b -- ) res *= a;
    return res;
}

LL calc(LL x, LL dep, LL k)
{
    if (dep + k < depn) return power(2, k);
    else if (dep + k == depn)
    {
        LL id = x - power(2, dep - 2), mb = power(2, k), di = n - power(2, depn - 1) + 1;
        if ((di + mb - 1) / mb < id) return 0;
        else if ((di + mb - 1) / mb == id) return di % mb;
        else return mb;
    }
    else return 0;
}

int main()
{
    LL T;
    scanf("%lld", &T);
    for (LL i = 1; i <= T; i ++ )
    {
        LL x, k;
        scanf("%lld%lld%lld", &n, &x, &k);
        if (!k)
        {
            printf("1\n");
            continue;
        }
        LL depx = (LL)log2(x) + 1, bd = depx, bk = k;
        depn = (LL)log2(n) + 1;
        LL res = 0;
        res += calc(x, depx, k); k -= 2;
        if (x + 1 <= n && k >= 0) res += calc(x + 1, depx, k);
        if (k >= 0) k -- ;
        x /= 2;
        while (depx >= 1 && k >= 0 && x / 2 > 0)
        {
            res += calc(x, depx, k);
            depx -- , k -- , x /= 2;
        }
        if (bd - bk >= 1) res ++ ;
        printf("%lld\n", res);
    }
    return 0;
}