포털 총과 케이크

$R \times C$ 크기의 격자에 서 있고, 같은 격자의 다른 칸에 케이크가 놓여 있다. 배가 몹시 고프기 때문에 되도록 적은 이동 횟수로 케이크가 있는 칸에 도착하려고 한다. 한 번 이동할 때 북, 남, 동, 서 중 한 방향에 있는 빈 칸으로 갈 수 있다.

손에는 포털 총이 있다. 이 총은 노란 포털과 파란 포털, 두 종류를 쏜다. 북, 남, 동, 서 중 한 방향으로 쏘면 에너지 덩어리가 그 방향으로 직선으로 날아가, 처음 만난 벽에 그 색 포털을 만든다. 포털은 에너지 덩어리가 날아온 쪽 벽면에 생긴다. 포털 총을 쏘는 것은 이동으로 세지 않는다. 에너지 덩어리는 케이크를 그대로 통과한다.

노란 포털과 파란 포털이 모두 있으면 한쪽 포털로 들어가 다른 쪽 포털로 나올 수 있다. 나올 때는 반대쪽 포털을 마주 보는 빈 칸에 서게 되고, 포털을 통과하는 것도 이동 한 번으로 센다. 두 색이 모두 놓이기 전에는 포털을 쓸 수 없다.

다음 격자를 보자.

회색 칸은 벽, 흰 칸은 빈 칸이고, 빨간 원이 자신의 위치다.

동쪽으로 파란 포털을 쏘면 처음 만난 벽에 포털이 생긴다.

이어서 남쪽으로 노란 포털을 쏜다.

남쪽으로 한 칸 이동한다.

여기서 남쪽으로 한 칸 더 이동하면 노란 포털로 들어가 파란 포털로 나온다.

같은 순간에 노란 포털과 파란 포털은 각각 최대 하나만 존재한다. 예를 들어 서쪽으로 파란 포털을 다시 쏘면 원래 있던 파란 포털은 사라진다.

포털은 같은 색 포털을 다시 쏠 때만 사라진다.

포털은 벽의 한쪽 면에 생긴다. 어떤 벽의 동쪽 면에 포털이 있다면 그 벽으로 동쪽에서 들어가야 포털을 통과한다. 다른 면에서 그 벽으로 들어가면 그냥 벽에 부딪힐 뿐이다.

한 벽면에 포털 두 개를 겹쳐 놓을 수는 없다. 이미 포털이 있는 벽면을 향해 쏘면 그 발사는 실패하고 아무것도 바뀌지 않는다.

격자와 시작 위치, 케이크의 위치가 주어질 때 케이크에 도착하는 최소 이동 횟수를 구한다. 도착할 방법이 없으면 그 사실을 답한다. 포털 총을 쏘는 것은 이동 횟수에 들어가지 않는다.

첫 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $R$과 $C$가 공백 하나로 구분되어 주어진다. 다음 $R$개의 줄에는 격자를 나타내는 $C$개의 문자가 주어진다.

• .은 빈 칸이다.
• #은 벽이다.
• O는 시작 위치다.
• X는 케이크의 위치다.

각 테스트 케이스에서 O와 X는 정확히 하나씩 나온다.

격자 밖의 칸은 모두 벽이고, 그 벽에도 포털을 만들 수 있다.

제한

• $1 \le N \le 200$
• $1 \le R, C \le 8$

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 케이크에 도착하는 최소 이동 횟수다. 케이크에 도착할 수 없으면 $y$ 자리에 THE CAKE IS A LIE를 출력한다.

첫 번째 테스트 케이스는 다음 순서로 4번 이동해 케이크에 도착한다. 포털 총을 쏘는 것은 이동 횟수에 들어가지 않는다.

1. 동쪽으로 한 칸 이동한다.
2. 북쪽으로 파란 포털을 쏜다.
3. 남쪽으로 노란 포털을 쏜다.
4. 북쪽으로 한 칸 이동해 파란 포털을 통과한다.
5. 동쪽으로 파란 포털을 쏜다.
6. 남쪽으로 한 칸 이동해 노란 포털을 통과한다.
7. 서쪽으로 한 칸 이동한다.
8. 케이크를 먹는다.

두 번째 테스트 케이스에서는 벽이 하나도 없지만 격자 밖이 모두 벽이므로 포털을 만들 수 있고, 두 번의 이동으로 대각선 반대편 칸에 도착한다.