{"problem":{"name":"Complete Binary Tree","description":{"content":"There is a tree with $N$ vertices numbered $1$ to $N$. For each $i\\ (2 \\leq i \\leq N)$, there is an edge connecting vertex $i$ and vertex $\\lfloor \\frac{i}{2} \\rfloor$. There are no other edges. In th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc321_e"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N$ vertices numbered $1$ to $N$. For each $i\\ (2 \\leq i \\leq N)$, there is an edge connecting vertex $i$ and vertex $\\lfloor \\frac{i}{2} \\rfloor$. There are no other edges.\nIn this tree, find the number of vertices whose distance from vertex $X$ is $K$. Here, the distance between two vertices $u$ and $v$ is defined as the number of edges in the simple path connecting vertices $u$ and $v$.\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1\\leq T \\leq 10^5$\n*   $1\\leq N \\leq 10^{18}$\n*   $1\\leq X \\leq N$\n*   $0\\leq K \\leq N-1$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format, where $\\mathrm{test}_i$ represents the $i$\\-th test case:\n\n$T$\n$\\mathrm{test}_1$\n$\\mathrm{test}_2$\n$\\vdots$\n$\\mathrm{test}_T$\n\nEach test case is given in the following format:\n\n$N$ $X$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc321_e","tags":[],"sample_group":[["5\n10 2 0\n10 2 1\n10 2 2\n10 2 3\n10 2 4","1\n3\n4\n2\n0\n\nThe tree for $N=10$ is shown in the following figure.\n![image](https://img.atcoder.jp/abc321/0d1a718458ffcf25a6bc26d11b3a7641.png)\nHere,\n\n*   There is $1$ vertex, $2$, whose distance from vertex $2$ is $0$.\n*   There are $3$ vertices, $1,4,5$, whose distance from vertex $2$ is $1$.\n*   There are $4$ vertices, $3,8,9,10$, whose distance from vertex $2$ is $2$.\n*   There are $2$ vertices, $6,7$, whose distance from vertex $2$ is $3$.\n*   There are no vertices whose distance from vertex $2$ is $4$."],["10\n822981260158260522 52 20\n760713016476190629 2314654 57\n1312150450968417 1132551176249851 7\n1000000000000000000 1083770654 79\n234122432773361868 170290518806790 23\n536187734191890310 61862 14\n594688604155374934 53288633578 39\n1000000000000000000 120160810 78\n89013034180999835 14853481725739 94\n463213054346948152 825589 73","1556480\n140703128616960\n8\n17732923532771328\n65536\n24576\n2147483640\n33776997205278720\n7881299347898368\n27021597764222976"]],"created_at":"2026-03-03 11:01:14"}}