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$

源代码：

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$