Pku3889 Fractal Streets

随着城市规模不断扩大，现代化建设对街道设计提出了新的要求。城市规划师 Chris 需要为一座全新的城市设计街道。为了减少工作量，他采用了朋友 Paul 提出的“分形街道”方案：使用希尔伯特曲线规划街道。

$1$ 阶希尔伯特曲线由一个杯形结构组成。对于 $2$ 阶希尔伯特曲线，将这个杯形结构替换为 $4$ 个更小但形状相同的杯形结构，并用 $3$ 条道路连接。对于 $3$ 阶希尔伯特曲线，再将其中的每个杯形结构按相同方式替换。更高阶的曲线依此递归构造。

每个杯形结构的各个拐角处都设有一条住宅车道和一个邮箱，所有住宅按照曲线上的先后顺序连续编号。左上角住宅的编号为 $1$，相邻两座住宅之间的距离为 $10$ 米。

一些市长向 Chris 提供了采用这种方案建设的住宅。每个街区中都有一座当地城市规划办公室。Chris 想知道，从获赠住宅到办公室的直线距离是多少。

Chris 可以驾驶飞行汽车直接从住宅车道飞往办公室车道，因此不需要沿街道行驶。请计算每组方案中他需要飞行的水平直线距离，不计起飞和降落时的垂直距离。

输入格式

第一行包含一个正整数，表示测试用例的数量。

接下来每组测试用例包含一行，其中有 $3$ 个正整数 $n$、$h$ 和 $o$，分别表示希尔伯特曲线的阶数、获赠住宅的编号和当地城市规划办公室的编号。

输出格式

对于每组测试用例，输出一行，表示 Chris 从住宅飞往办公室的距离，单位为米。

结果四舍五入到最接近的整数。

样例输入

3
1 1 2
2 16 1
3 4 33

样例输出

10
30
50

数据范围

• $n<16$；
• $h<2^{31}$，$o<2^{31}$；
• $1\le h,o\le 4^n$；
• $n$、$h$ 和 $o$ 均为正整数。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3
1 1 2
2 16 1
3 4 33

输出

10
30
50