포털

R행 C열 격자 안에 있다. 격자의 다른 어딘가에는 케이크가 놓여 있고, 되도록 적은 이동 횟수로 케이크가 있는 칸까지 가야 한다. 한 번 이동할 때마다 북, 남, 동, 서 중 한 방향으로 빈 칸 하나만큼 움직인다.

들고 있는 포털 건은 노란 포털과 파란 포털을 쏜다. 북, 남, 동, 서 중 한 방향으로 포털 건을 쏘면 에너지 구슬이 그 방향으로 날아가고, 구슬이 처음 만나는 벽에 포털이 생긴다. 포털 건을 쏘는 것은 이동 횟수에 들어가지 않는다. 케이크를 향해 쏘면 구슬은 케이크를 그대로 통과한다.

노란 포털과 파란 포털이 모두 생긴 뒤에는 노란 포털로 들어가 파란 포털로 나올 수 있고, 반대 방향으로도 갈 수 있다. 포털은 두 색이 모두 놓인 뒤에만 쓸 수 있다.

다음 격자를 보자.

회색 칸은 벽, 흰 칸은 빈 칸이고 빨간 원이 현재 위치다.

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

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

남쪽으로 한 칸 이동한다.

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

노란 포털과 파란 포털은 언제나 각각 하나씩만 존재한다. 예를 들어 파란 포털을 서쪽으로 새로 쏘면 먼저 있던 파란 포털은 사라진다.

포털이 사라지는 것은 같은 색을 다시 쏠 때뿐이다.

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

포털 두 개를 같은 면에 겹쳐 놓을 수는 없다. 이미 포털이 있는 벽면을 향해 다른 포털을 쏘면 두 번째 포털은 생기지 않는다.

미로와 시작 위치, 케이크의 위치가 주어질 때 케이크가 있는 칸에 도달하는 최소 이동 횟수를 구하라. 포털 건을 쏘는 것은 이동 횟수에 들어가지 않는다.

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

각 테스트 케이스의 첫 줄에 두 정수 R과 C가 공백으로 구분되어 주어진다. 이어지는 R개의 줄에는 각각 C개의 문자가 주어져 지도를 나타낸다.

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

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

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

제한:

• $1 \le N \le 50$
• $1 \le R \le 15$
• $1 \le C \le 15$

각 테스트 케이스마다 한 줄에 Case #X: Y 형식으로 출력한다. X는 테스트 케이스 번호이고, Y는 케이크에 도달하는 최소 이동 횟수다. 케이크에 도달할 수 없으면 Y 자리에 THE CAKE IS A LIE를 출력한다.

첫 번째 예제의 첫 테스트 케이스는 다음 순서로 네 번 이동해 케이크에 도달한다. 포털 건을 쏘는 것은 이동 횟수에 들어가지 않는다.

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