你正在玩一款名为“希尔伯特迷宫”（Hilbert’s Maze）的电脑游戏。游戏的目的是在各种迷宫中找到出路。游戏的最后一关包含了一个最棘手的迷宫，你发现很难从中逃脱。由于对迷宫的复杂性感到沮丧，你决定运用你的编程技能来解决它。

迷宫可以描述为一个被划分为相同正方形单元格的矩形区域，单元格的某些边界上有墙。站在一个单元格中，如果没有墙阻挡，你可以移动到任何相邻的单元格（如果两个单元格共享一条边界线，则它们是相邻的）。

你即将逃离的特定迷宫可以通过以下递归模式构建：从基础迷宫 $T_0$（图 1）开始，应用以下变换（图 2）$k$ 次，即可得到最终的迷宫 $T_k$。你引入了如图 2 所示的坐标系，左下角的单元格坐标为 $(1, 1)$。例如，迷宫 $T_2$ 如图 3 所示。

图 1、图 2、图 3

你可以逃离迷宫的边界（即以 $(1, 1)$ 和 $(2^{k+1} - 1, 2^{k+1} - 1)$ 为角的正方形区域）；边界外没有墙，你可以沿着边界移动，或者根据需要远离迷宫。你需要找到从某个起始单元格到某个目标单元格的最短路径。起始和目标单元格每次尝试时都是随机生成的，因此你希望编写一个程序来解决该问题的多个实例。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 3 \cdot 10^5$)，表示测试用例的数量。

接下来的 $T$ 行包含测试用例的描述。第 $i$ 行包含五个空格分隔的整数 $k, x_s, y_s, x_t, y_t$ ($0 \le k \le 30, 1 \le x_s, y_s, x_t, y_t \le 2^{k+1} - 1$)，分别表示用于构建迷宫的变换次数以及起始单元格和目标单元格的坐标。起始单元格和目标单元格可能重合。

输出格式

输出 $T$ 行；在第 $i$ 行打印一个整数，表示从起始单元格到达目标单元格所需的最少移动步数。保证单元格之间存在路径。

样例

输入 1

3
0 1 1 1 1
1 1 3 3 3
1 1 1 3 3

输出 1

0
4
8

说明

第二个和第三个样例的示意图如下。