무한 정원 (Large)

문제

파스칼 왕국의 왕은 미로를 아주 좋아한다. 어느 날 왕은 신하에게 성의 넓은 정원을 뒤덮는 미로를 만들라고 명령했다. 성의 정원은 무한히 넓으니 만만한 명령이 아니었다. 성이 있는 자리를 원점으로 두고 $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만큼 곧장 나아간 뒤 동쪽으로 방향을 바꾼다. 그다음부터는 그림과 같이 나아간다.

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

프로그램은 두 점 $P$ , $Q$ 의 좌표를 받아 미로 안에서의 최단 거리를 출력한다. 문제를 간단히 하기 위해, 거리를 재는 경로는 $X$ 축에 수직이거나 평행한 선분으로만 이루어진다고 하자. 벽은 지나갈 수 없지만 벽 자체는 한없이 얇아서, 벽이 놓인 선에는 얼마든지 가까이 다가갈 수 있다. 이렇게 정의한 최단 거리는 언제나 정수이다.

입력

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $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 240$
$P_x$ , $P_y$ , $Q_x$ , $Q_y$ 는 모두 짝수이다.

출력

각 테스트 케이스마다

Case #X: L

형식의 문자열을 한 줄에 출력한다. $X$ 는 1부터 시작하는 테스트 케이스 번호이고, $L$ 은 점 $P$ 에서 점 $Q$ 까지 본문에서 정의한 경로를 따라갔을 때의 최단 거리이다.