무한 정원 (Small)

문제

파스칼 왕국의 왕은 미로를 좋아한다. 어느 날 왕은 신하에게 성의 넓은 정원을 덮는 미로를 만들라고 명령했다. 성의 정원이 무한히 넓어서 이것은 만만치 않은 지시였다. 성의 위치를 원점에 두고 $X$ 축을 동쪽, $Y$ 축을 북쪽으로 잡으면 정원은 $X \ge 0$ , $Y \ge 0$ 인 영역 전체다.

뛰어난 로봇 공학자인 당신은 정원 손질 로봇을 개조해서 정원에 미로를 그리는 로봇을 만들었다. 이 로봇은 A 모드와 B 모드, L과 X와 R 문자가 이어져 적힌 테이프, 테이프의 한 칸을 가리키는 읽기 헤드로 이루어진다. 로봇은 헤드가 가리키는 문자를 읽어서 움직임을 바꾼다. 헤드는 앞에서 뒤로 한 방향으로만 움직이지만, 로봇은 이미 읽은 부분까지 포함한 테이프 전체를 복사해서 테이프 끝에 붙이는 방식으로 계속 읽어 나간다. 로봇은 테이프의 아무 칸이나 고쳐 쓸 수도 있다.

로봇은 다음 처리를 순서대로 되풀이한다.

헤드가 테이프의 마지막 문자를 가리키고 있으면 모드에 따라 다음 중 하나를 한다.
- A 모드면 테이프의 첫 문자가 X이면 L로, L이면 X로 고쳐 쓴다. 그다음 테이프 전체를 복사하고, 복사본에서 L은 R로 R은 L로 바꾼 뒤 테이프 끝에 붙인다. 그리고 모드를 B로 바꾼다.
- B 모드면 테이프 전체를 복사하고, 복사본의 앞뒤를 뒤집은 뒤 테이프 끝에 붙인다. 그리고 모드를 A로 바꾼다.
바라보는 방향으로 거리 2만큼 나아가고 헤드를 한 칸 앞으로 옮긴다.
헤드가 가리키는 문자를 읽는다. L이면 왼쪽으로 90도 돌고, R이면 오른쪽으로 90도 돈다. X면 방향을 그대로 둔다.

로봇을 좌표 $(1, 1)$ 에 놓고 $Y$ 축 양의 방향을 바라보게 한 다음, X 한 글자만 적힌 테이프를 읽힌다. 처음 모드는 A이고 헤드는 그 X를 가리킨다. 이 상태에서 로봇을 켜면 로봇은 정원을 끝없이 돌아다닌다. 로봇이 지나간 자취를 미로의 벽으로 삼으면 복잡한 미로가 만들어진다. 왕은 당신의 이 업적을 칭찬했다.

그림은 로봇의 첫 여덟 걸음과 그 사이의 상태 변화다. 테이프에서 대괄호로 감싼 문자가 헤드가 가리키는 칸이다. $(1, 1)$ 에서 출발한 로봇은 곧바로 테이프를 늘린 뒤 북쪽으로 2만큼 곧장 나아가고 동쪽으로 방향을 바꾼다.

미로가 너무 복잡해서 안에서 빠져나오지 못하면 그것도 곤란하다. 왕은 로봇이 그린 미로를 검증하라고 명령했고, 당신은 미로 안의 지정된 두 점 사이의 최단 거리를 구하는 프로그램을 만들기로 했다.

거리를 재는 경로는 $X$ 축에 평행하거나 수직인 선분으로만 이루어진다. 경로는 정원 밖으로 나갈 수 없고 벽을 가로지를 수도 없다. 다만 벽의 두께는 0이므로 경로는 벽이 놓인 직선에 얼마든지 가까이 붙을 수 있다. 두 점 사이의 최단 거리는 이런 경로 길이의 하한이고, 항상 정수다.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에 각각 공백으로 구분된 짝수 네 개 $P_x$ , $P_y$ , $Q_x$ , $Q_y$ 가 주어진다.

점 $(P_x, P_y)$ 와 $(Q_x, Q_y)$ 에는 벽이 없다. 벽 위의 점은 두 좌표 중 적어도 하나가 홀수이기 때문이다.

제한

$1 \le T \le 100$
$0 \le P_x, P_y, Q_x, Q_y \le 32$
$P_x$ , $P_y$ , $Q_x$ , $Q_y$ 는 모두 짝수다.

출력

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #x: y

$x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 점 $P$ 에서 점 $Q$ 까지 본문에서 정의한 경로로 갔을 때의 최단 거리다.