Here-There

Here-There is a virtual board game played on a recursively perforated square board.

To build a board of degree D, start with a square whose side length is 3^D. Divide it into nine equal smaller squares and remove the center square. Then repeat the same divide-and-remove process on each remaining square, D times in total, until every remaining cell has side length 1.

In one round, an opponent chooses two remaining cells. One cell is Here and the other is There. You must find the minimum number of steps needed to move from Here to There. One step moves to a remaining cell that shares a side with the current cell. Removed parts of the board cannot be entered or crossed.

Each cell is described by two 1-based coordinates. The first coordinate is the column and the second coordinate is the row. The upper-left cell has coordinates (1, 1).

The next picture shows one shortest path from (1, 1) to (4, 8), consisting of 10 steps.

Given several boards and pairs of cells, compute the step distance between the two cells for each pair.

The first line contains an integer T, the number of test cases. A blank line may appear before each test case.

Each test case contains five integers D, Hc, Hr, Tc, Tr. D is the degree of the board, (Hc, Hr) is the coordinate of Here, and (Tc, Tr) is the coordinate of There.

For each test case, output one line containing one integer: the step distance from Here to There.