AT_abc321_e [ABC321E] Complete Binary Tree

[problemUrl]: https://atcoder.jp/contests/abc321/tasks/abc321_e $ 1 $ から $ N $ までの番号が付けられた $ N $ 頂点からなる木があります。 各 $ i\ (2\ \leq\ i\ \leq\ N) $ について、頂点 $ i $ と頂点 $ \lfloor\ \frac{i}{2}\ \rfloor $ を結ぶ辺が張られています。 逆に、これら以外の辺は存在しません。 この木において、頂点 $ X $ との距離が $ K $ である頂点の数を求めてください。 ただし、$ 2 $ 頂点 $ u,v $ の距離は、頂点 $ u,v $ を結ぶ単純パスに含まれる辺の個数として定義されます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 ここで、$ \mathrm{test}_i $ は $ i $ 番目のテストケースを意味する。 > $ T $ $ \mathrm{test}_1 $ $ \mathrm{test}_2 $ $ \vdots $ $ \mathrm{test}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ X $ $ K $

$ T $ 行出力せよ。 $ i\ (1\ \leq\ i\ \leq\ T) $ 行目には、$ i $ 番目のテストケースに対する答えを整数として出力せよ。

### 制約 - $ 1\leq\ T\ \leq\ 10^5 $ - $ 1\leq\ N\ \leq\ 10^{18} $ - $ 1\leq\ X\ \leq\ N $ - $ 0\leq\ K\ \leq\ N-1 $ - 入力は全て整数 ### Sample Explanation 1 $ N=10 $ のとき、木は以下の図のようになります。 !\[\](https://img.atcoder.jp/abc321/0d1a718458ffcf25a6bc26d11b3a7641.png) このとき、 - 頂点 $ 2 $ との距離が $ 0 $ である頂点は $ 2 $ の $ 1 $ つです。 - 頂点 $ 2 $ との距離が $ 1 $ である頂点は $ 1,4,5 $ の $ 3 $ つです。 - 頂点 $ 2 $ との距離が $ 2 $ である頂点は $ 3,8,9,10 $ の $ 4 $ つです。 - 頂点 $ 2 $ との距離が $ 3 $ である頂点は $ 6,7 $ の $ 2 $ つです。 - 頂点 $ 2 $ との距離が $ 4 $ である頂点は存在しません。