Hilbert's Maze

You are playing a computer game "Hilbert's Maze". The goal of the game is to find a way out of various mazes. The last level has the trickiest maze, and you cannot find your way out of it. Tired of the maze's complexity, you decide to use your programming skills instead.

The maze is a rectangular field divided into identical square cells, with walls along some cell borders. While standing in a cell, you can move to an adjacent cell (two cells are adjacent if they share a border segment) when no wall blocks the way.

The maze is built with the following recursive rule. Start from the basic maze $T_0$ (Figure 1), and apply the transformation shown in Figure 2 $k$ times to get the resulting maze $T_k$. The coordinate system is shown in Figure 2, with the cell in the lower left corner at $(1, 1)$. For example, $T_2$ is shown in Figure 3.

Figure 1	Figure 2	Figure 3

You can leave the maze. The square with corners $(1, 1)$ and $(2^{k+1}-1, 2^{k+1}-1)$ is the boundary, and there are no walls outside it. You can walk along the border or move as far from the maze as you like. Find the shortest path from the start cell to the target cell. Start and target cells are chosen at random for each attempt, so you want a program that finds shortest paths for many instances.

The first line contains an integer $T$ ($1 \leq T \leq 3 \cdot 10^5$), the number of test cases. Each of the next $T$ lines contains five space-separated integers $k$, $x_s$, $y_s$, $x_t$, $y_t$ ($0 \leq k \leq 30$, $1 \leq x_s, y_s, x_t, y_t \leq 2^{k+1}-1$). Here $k$ is the number of transformations used to build the maze, $(x_s, y_s)$ is the start cell, and $(x_t, y_t)$ is the target cell. The two cells may coincide.

Print $T$ lines. The $i$-th line contains the minimum number of moves from the start cell to the target cell in the $i$-th test case. It is guaranteed that a path between the two cells exists.

The figure below illustrates the second and third samples.