Description

题目描述

有一棵树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。每个 $i(2 \leq i \leq N)$ 都有一条边连接顶点 $i$ 和顶点 $\lfloor \frac{i}{2} \rfloor$ 。没有其他边。

在这棵树中，找出与顶点 $X$ 的距离为 $K$ 的顶点个数。这里，两个顶点 $u$ 和 $v$ 之间的距离定义为连接顶点 $u$ 和 $v$ 的简单路径上的边的数量。

您有 $T$ 个测试用例要解决。

输入格式

第一行$T$

接下来$T$行每行三个变量$N，X，K$

输出格式

$T$行，每行一个答案

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

1
3
4
2
0

10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

说明/提示

对于 $20\%$ 的数据，$1\le N\le100$

对于 $50\%$ 的数据，$1\le N\le 10^9$

对于 $100\%$ 的数据，$1\le N\le10^{18},1 \le X \le N,0 \le K\le N-1$，$1 \le T \le 10^4$