该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面翻译

zlt 有一棵树，编号为 $1$ 至 $N$。对于每个 $i (2 \le i \le N)$，有一条边连接顶点 $i$ 和顶点 $\lfloor \frac{i}{2} \rfloor$。

于是 liangbowen 有一个问题：找出与顶点 $X$ 的距离为 $K$ 的顶点个数。然而他不会求解，于是来询问你。

这里，两个顶点 $u$ 和 $v$ 之间的距离定义为连接顶点 $u$ 和 $v$ 的简单路径中的边的数量。

本题为多组数据。

$1 \le T \le 10^5,1 \le N \le 10^{18},1 \le X \le N,0 \le K \le N-1$

from

题目描述

$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

样例输入 #1

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

样例输出 #1

1
3
4
2
0

样例 #2

样例输入 #2

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

样例输出 #2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

提示

制約

• $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$ のとき、木は以下の図のようになります。  このとき、 - 頂点 $2$ との距離が $0$ である頂点は $2$ の $1$ つです。 - 頂点 $2$ との距離が $1$ である頂点は $1,4,5$ の $3$ つです。 - 頂点 $2$ との距離が $2$ である頂点は $3,8,9,10$ の $4$ つです。 - 頂点 $2$ との距離が $3$ である頂点は $6,7$ の $2$ つです。 - 頂点 $2$ との距離が $4$ である頂点は存在しません。