EZ-소코반 (스몰)

문제

소코반은 창고지기가 상자를 정해진 자리로 밀어 넣는 퍼즐이다. 상자를 밀려면 상자 바로 뒤 칸과 바로 앞 칸이 모두 비어 있어야 한다. 미는 사람이 상자 뒤에 서야 하고, 한 번에 상자 하나만 밀 수 있기 때문이다. 상자를 판 밖으로 밀 수 없고, 상자를 밀 때 판 밖에 설 수도 없다.

아래 그림을 보자.

1번 상자는 인접한 네 칸이 모두 비어 있어서 네 방향 모두로 밀 수 있다. 2번 상자는 동쪽과 서쪽으로만 밀 수 있다. 남쪽 칸이 비어 있지 않아서 북쪽이나 남쪽으로는 밀 수 없다. 3번 상자는 어느 방향으로도 밀 수 없다. 4번 상자는 남쪽에 벽이 있어서 동쪽과 서쪽으로만 밀 수 있다.

일반적인 소코반은 PSPACE-완전 문제이지만, 여기서는 더 쉬운 변형을 다룬다. 이 변형에서 상자에는 강한 자석이 들어 있어서 거의 항상 서로 붙어 있어야 한다. "안정" 상태에서는 모든 상자가 변끼리 이어져 하나로 연결되어 있다. 즉 어떤 상자에서 출발해도 변을 공유하는 상자만 밟아 다른 모든 상자에 도달한다. 상자를 밀어서 연결이 끊어지면 "위험" 상태가 된다. 위험 상태에서는 바로 다음 밀기로 상자를 다시 연결해야 한다.

아래 그림을 보자.

상자 네 개가 모두 변끼리 이어져 있으니 안정 상태다. 여기서 가장 북쪽 상자를 서쪽으로 밀었다고 하자.

가장 북쪽 상자가 다른 어떤 상자와도 붙어 있지 않으므로 위험 상태다. 다음 밀기로 안정 상태로 돌아가야 한다. 예를 들어 그 상자를 남쪽으로 밀면 된다.

상자가 다시 안정 상태가 된다.

퍼즐은 판, 상자의 처음 배치, 상자가 마지막에 있어야 할 배치로 이루어진다. 상자를 미는 횟수가 가장 적은 해법을 찾거나, 풀 수 없다고 판정하라. 처음 배치와 마지막 배치는 모두 안정 상태다.

문제를 단순하게 만들기 위해, 창고지기는 언제든 판 위의 빈 칸 아무 곳으로나 순간 이동할 수 있다고 가정한다.

입력

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

각 테스트 케이스의 첫 줄에는 판의 행 수 $R$ 과 열 수 $C$ 가 공백 하나로 구분되어 주어진다. 이어서 $R$ 개의 줄에 각각 $C$ 개의 문자가 주어져 판을 나타낸다.

'.'는 빈 칸
'#'는 벽
'x'는 목표 칸, 즉 마지막에 상자가 있어야 하는 칸
'o'는 상자
'w'는 상자와 목표 칸이 겹친 칸

상자의 개수와 목표 칸의 개수는 같다.

제한

$1 \le T \le 50$
$1 \le R, C \le 12$
상자의 개수는 1 이상 3 이하다.
상자의 처음 배치와 마지막 배치는 모두 안정 상태다.

출력

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

Case #X: K

$X$ 는 1부터 시작하는 테스트 케이스 번호이고, $K$ 는 퍼즐을 푸는 데 필요한 최소 밀기 횟수다. 풀 수 없으면 $K$ 자리에 -1을 출력한다.