힐베르트 미로

당신은 컴퓨터 게임 "Hilbert's Maze"를 하고 있다. 이 게임의 목표는 여러 미로에서 출구를 찾는 것이다. 마지막 단계에는 가장 까다로운 미로가 있는데, 당신은 그 미로에서 빠져나가는 길을 찾지 못하고 있다. 복잡한 미로에 지친 당신은 프로그래밍 실력을 활용해 보기로 한다.

미로는 크기가 같은 정사각형 칸들로 나뉜 직사각형 격자이며, 일부 칸의 경계에는 벽이 있다. 어떤 칸에 서 있을 때, 인접한 칸(두 칸이 변을 공유하면 인접하다)으로 가는 길에 벽이 없으면 그 칸으로 이동할 수 있다.

이 미로는 다음 재귀 규칙으로 만들어진다. 기본 미로 $T_0$(그림 1)에서 시작해 그림 2의 변환을 $k$번 적용하면 결과 미로 $T_k$를 얻는다. 좌표계는 그림 2와 같으며, 왼쪽 아래 칸의 좌표는 $(1, 1)$이다. 예를 들어 $T_2$는 그림 3과 같다.

그림 1	그림 2	그림 3

미로 바깥으로 나갈 수 있다. $(1, 1)$과 $(2^{k+1}-1, 2^{k+1}-1)$을 모서리로 하는 정사각형이 경계이며, 그 바깥에는 벽이 없다. 경계를 따라 걸을 수도 있고, 미로에서 얼마든지 멀리 떨어져 걸을 수도 있다. 시작 칸에서 목표 칸까지의 최단 경로를 구해야 한다. 시작 칸과 목표 칸은 시도할 때마다 무작위로 정해지므로, 많은 문제 사례에 대해 최단 경로를 구하는 프로그램을 작성하고자 한다.

첫 줄에 테스트 케이스의 수 $T$ ($1 \leq T \leq 3 \cdot 10^5$)가 주어진다. 다음 $T$개의 줄에는 각각 공백으로 구분된 정수 다섯 개 $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$)가 주어진다. $k$는 미로를 만들 때 변환을 적용한 횟수이고, $(x_s, y_s)$는 시작 칸, $(x_t, y_t)$는 목표 칸이다. 두 칸은 같을 수도 있다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트 케이스에서 시작 칸부터 목표 칸까지 가는 데 필요한 최소 이동 횟수를 출력한다. 두 칸 사이에 경로가 존재함이 보장된다.

아래 그림은 두 번째와 세 번째 예제를 나타낸다.