题目描述

给你一棵有 $n$ 个点的完全二叉树，且除了 $1$ 号点为根之外，$i$ 号点的父亲都是 $\lfloor \frac{i}{2}\rfloor$。

现在强哥想知道和 $x$ 号节点之间的简单路径的长度为 $y$ 的点的数量。你能告诉他吗？

输入格式

输入的第一行为一个数 $T$，表示询问的组数。

对于每一组询问输入一行三个数 $n,x,y$。

输出格式

每组询问输出一行，表示满足要求的点的数量。

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

数据范围

• $1\leq\ T\ \leq\ 10^5$
• $1\leq\ n\ \leq\ 10^{18}$
• $1\leq\ x\ \leq\ n$
• $0\leq\ y\ \leq\ n-1$