题目描述

艾扎克身处一个迷宫之中！迷宫可看作是一个有 $n$ 个结点的树形结构. 对于每个结点 $i$ ($2 \le i \le n$) , 都有一条边连接着结点 $i$ 与结点 $\lfloor \frac{i}{2} \rfloor$ . 艾扎克现在位于结点 $x$ . 由于受到迷途诅咒的影响，艾扎克忘记了迷宫的样子. 请你告诉他迷宫中距离结点 $x$ 的距离为 $k$ 的点有多少个.

对于每个测试用例，你需要回答 $T$ 组询问.

输入格式

第 $1$ 行，询问数 $T$ 。

接下来 $T$ 行，每行 $3$ 个数字 $n,x,k$.

输出格式

对于每个询问，输出一个整数表示迷宫中距离结点 $x$ 的距离为 $k$ 的点的个数.

样例输入

3
10 2 1
10 2 2
10 2 3

样例输出

3
4
2

数据范围

对于 $10\%$ 的数据，满足 $T \le 3$, $1 \le x \le n \le 2000$, $0 \le k \le n-1$

对于 $30\%$ 的数据，满足 $T \le 3$, $1 \le x \le n \le 10^5$, $0 \le k \le n-1$

对于 $100\%$ 的数据，满足 $T \le 10^5$, $1 \le x \le n \le 10^{18}$, $0 \le k \le n-1$