以下、頂点 \(1\) を根とした根つき木として考えます。

本問題で与えられる木は完全二分木の一種であり、以下のような特徴があることから、しばしば問題の題材やデータ構造（segment tree など）の実装手段として用いられます。

• 木の高さが \(\log_2N\) である
• 頂点 \(i\) の親、左の子、右の子の番号がそれぞれ \(\lfloor \frac{i}{2} \rfloor,2i, 2i+1\) と簡単な形で表せる

後者の特徴から、更に以下の事実が導けます。

• 頂点 \(i\) の子孫であって、頂点 \(i\) との距離が \(d\) である頂点の番号の集合は、区間 \([i\times 2^d, (i+1)\times 2^d)\) と \([1,N]\) の共通区間である（＊）

ここからは本問題について考えます。頂点 \(X\) との距離が \(K\) である頂点を \(Y\) とし、\(X\) と \(Y\) の最小共通祖先を \(Z\) とおきます。木の高さが \(\log_2N\) であることから \(Z\) としてありうるものは高々 \(\log_2N+1\) 通りしかなく、また \(Z\) を固定したときに「\(X\) との最小共通祖先が \(Z\) であり、\(X\) との距離が \(K\) であるような頂点 \(Y\) の数」は事実（＊）を用いて \(O(1)\) で計算可能なことから、本問題はクエリあたり \(O(\log N)\) で解くことができます。

例えば、\(X=8,K=5\) であり、\(Z=2\) を固定したときのことを考えます。頂点 \(X,Z\) の距離は \(2\) ですから、「頂点 \(8\) との最小共通祖先が頂点 \(2\) であり、頂点 \(8\) との距離が \(5\) であるような頂点の数」は、「頂点 \(2\) の子孫であるが頂点 \(4\) の子孫ではない頂点のうち、頂点 \(2\) との距離が \(3\) であるような頂点の数」というように事実（＊）を適用可能な形へと言い換えることができます。ここから先は実装方針によりますが、条件を満たす頂点の区間を場合分けで陽に求めることも、「頂点 \(2\) の子孫であって、頂点 \(2\) との距離が \(3\) であるような頂点の数」から「頂点 \(4\) の子孫であって、頂点 \(4\) との距離が \(2\) であるような頂点の数」を引いて求めることもできます。以下の実装例では前者を用いています。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int depth(ll n) {
    int d = 0;
    while (true) {
        n >>= 1;
        if (!n) break;
        ++d;
    }
    return d;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, x, k;
        cin >> n >> x >> k;
        int dn = depth(n);
        int dx = depth(x);
        ll ans = 0;
        for (int i = 0; i <= dx; i++) { // i = depth(lca(x, y))
            if (dx - i > k) continue;
            if (i + k - (dx - i) > dn) continue;
            ll l, r;
            if (i == dx) {
                l = x << k;
                r = (x + 1) << k;
            } else {
                ll z = x >> (dx - i);
                if (dx - i < k) {
                    l = z * 2 + (~x >> (dx - i - 1) & 1);
                    l <<= (k - (dx - i) - 1);
                    r = l + (1LL << (k - (dx - i) - 1));
                } else {
                    l = z, r = z + 1;
                }
            }
            if (l > n) continue;
            r = min(r, n + 1);
            ans += r - l;
        }
        cout << ans << '\n';
    }
}