Hilbert's Hedge Maze

문제

David has elaborate hedge mazes in his garden. For each of his mazes of different sizes, he wonders how long it would take to walk between any pair of locations in and around that maze. A hedge maze of order $n\ge 1n\backslash geq\; 1$ is constructed according to very specific instructions:

1. Start with $S=AS=A$.
2. Repeat $nn$ times:
   1. Create a new string $TT$ by replacing each $AA$ in $SS$ with $LBFRAFARFBLLBFRAFARFBL$ and each $BB$ with $RAFLBFBLFARRAFLBFBLFAR$.
   2. Set $S=TS=T$.
3. Remove all $AA$'s and all $BB$'s from $SS$.

The resulting string gives the instructions for constructing the hedge maze. In the unbounded plane start at coordinates $(0,0)(0,0)$, facing towards $(1,0)(1,0)$ and for every $FF$ move forward one unit, for every $RR$ turn right $9090$ degrees, and for every $LL$ turn left $9090$ degrees.

After constructing the maze, identify position $(x,y)(x,y)$ with the unit square cell bounded by coordinates $(x,y),(x+1,y),(x,y+1),(x+1,y+1)(x,y),(x+1,y),(x,y+1),(x+1,y+1)$. We can move directly between two positions $(x_1,y_1)(x\_1,y\_1)$, $(x_2,y_2)(x\_2,y\_2)$ if and only if either $\mathrm{\mid }{x}_1-x_2\mathrm{\mid }=1|x\_1-x\_2|=1$ or $\mathrm{\mid }{y}_1-y_2\mathrm{\mid }=1|y\_1-y\_2|=1$, but not both, and there is no hedge between these cells. The distance between these two positions is $11$.

Given a number $nn$ and a pair of positions, find the shortest distance between these positions.

입력

Input starts with a positive integer $kk$ $(1\le k\le 100)(1\backslash leq\; k\backslash leq\; 100)$, denoting the number of test cases. Each of the next $kk$ lines consists of $55$ integers $nn$, $x_{1}x\_1$, $y_{1}y\_1$, $x_{2}x\_2$, $y_{2}y\_2$, satisfying $1\le n\le 501\backslash leq\; n\backslash leq\; 50$, and $-2^{52}\le x_1,y_1,x_2,y_2\le 2^{52}-2^\{52\}\backslash leq\; x\_1,y\_1,x\_2,y\_2\backslash leq\; 2^\{52\}$. There is no interaction between the test cases. Each specifies a single hedge maze situated alone in the unbounded plane.

출력

Output $kk$ lines with one integer on each line, corresponding to the shortest distance between the two positions in each of the $kk$ test cases.

힌트

The shortest path from the first case in the sample input.

2
3 5 3 4 0
2 4 3 0 2

16
11