힐베르트의 생울타리 미로

David은 정원에 정교한 생울타리 미로를 가지고 있다. 각 미로마다 미로 안이나 주변에 있는 임의의 두 위치 사이를 걸어서 이동하는 데 얼마나 걸리는지 알고 싶어 한다. 차수가 $n\geq 1$인 생울타리 미로는 다음 절차로 만든다.

1. $S=A$로 시작한다.
2. 다음 과정을 $n$번 반복한다.
   1. $S$의 각 $A$를 LBFRAFARFBL로, 각 $B$를 RAFLBFBLFAR로 바꾼 새 문자열 $T$를 만든다.
   2. $S=T$로 둔다.
3. $S$에서 모든 $A$와 $B$를 지운다.

남은 문자열이 미로를 만드는 지시어다. 무한 평면의 원점 $(0,0)$에서 $(1,0)$ 방향을 보고 출발한다. F는 한 단위 앞으로 이동, R은 오른쪽으로 90도, L은 왼쪽으로 90도 회전이다.

미로를 만든 뒤 위치 $(x,y)$는 꼭짓점이 $(x,y),(x+1,y),(x,y+1),(x+1,y+1)$인 단위 정사각형 칸과 대응한다. 두 위치 $(x_1,y_1)$, $(x_2,y_2)$는 $|x_1-x_2|=1$과 $|y_1-y_2|=1$ 중 하나만 성립하고 두 칸 사이에 생울타리가 없을 때 직접 이동할 수 있다. 이때 거리는 1이다. 주어진 $n$과 두 위치에 대해 최단 거리를 구하라.

시간 제한은 1000 ms, 메모리 제한은 1024 MB이다.

첫 줄에 테스트 케이스 수를 나타내는 양의 정수 $k$ $(1\leq k\leq 100)$가 주어진다. 이어지는 $k$개 줄에는 정수 5개 $n$, $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. 여기서 $1\leq n\leq 50$이고 $-2^{52}\leq x_1,y_1,x_2,y_2\leq 2^{52}$이다. 테스트 케이스끼리는 서로 영향을 주지 않으며, 각 케이스는 무한 평면에 홀로 놓인 미로 하나를 나타낸다.

$k$개 줄에 각 테스트 케이스의 두 위치 사이 최단 거리를 한 줄에 정수 하나씩 출력한다.

첫 번째 케이스의 최단 경로는 다음 그림과 같다.