Here-There

Here-There는 재귀적으로 구멍이 뚫린 정사각형 보드에서 하는 가상 보드게임이다.

차수 D인 보드는 한 변의 길이가 3^D인 정사각형에서 시작해 만든다. 정사각형을 같은 크기의 작은 정사각형 9개로 나누고, 가운데 정사각형을 제거한다. 그런 다음 남아 있는 각 정사각형에 대해 같은 분할과 가운데 제거 과정을 전체 D번 반복하면, 한 변의 길이가 1인 칸들과 구멍들로 이루어진 보드가 된다.

한 게임에서 상대는 남아 있는 두 칸을 고른다. 한 칸은 Here이고 다른 한 칸은 There이다. 여러분은 Here에서 There까지 이동하는 데 필요한 최소 걸음 수를 구해야 한다. 한 걸음은 현재 칸과 변을 공유하는 남아 있는 이웃 칸으로 이동하는 것이다. 제거된 부분으로 들어가거나 그 위를 지나갈 수는 없다.

각 칸은 1부터 시작하는 두 좌표로 표현한다. 첫 번째 좌표는 열, 두 번째 좌표는 행이다. 왼쪽 위 칸의 좌표는 (1, 1)이다.

다음 그림은 (1, 1)에서 (4, 8)까지 가는 최단 경로 중 하나를 보여 주며, 길이는 10걸음이다.

여러 보드와 두 칸의 쌍이 주어질 때, 각 쌍에 대해 두 칸 사이의 걸음 거리를 구하라.

첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 있을 수 있다.

각 테스트 케이스는 정수 D, Hc, Hr, Tc, Tr 다섯 개로 이루어진다. D는 보드의 차수이고, (Hc, Hr)는 Here의 좌표, (Tc, Tr)는 There의 좌표이다.

각 테스트 케이스마다 Here에서 There까지의 걸음 거리를 나타내는 정수 하나를 한 줄에 출력한다.