EZ-소코반

소코반은 일본에서 만든 유명한 퍼즐 게임이다. 이름은 창고를 지키는 사람을 뜻한다. 창고 안의 상자를 정해진 자리로 밀어 넣는 것이 목표다. 상자를 밀려면 상자 바로 뒤 칸과 바로 앞 칸이 모두 비어 있어야 한다. 밀 때는 상자 뒤에 서야 하고, 한 번에 상자 하나만 밀 수 있다. 상자를 판 밖으로 밀 수 없고, 상자를 밀면서 판 밖에 설 수도 없다.

아래 그림을 보자.

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

소코반은 PSPACE-완전 문제로 증명됐지만, 이 문제에서는 더 쉬운 변형을 다룬다. 이 변형에서는 상자마다 강한 자석이 들어 있어서 상자들이 거의 항상 붙어 있어야 한다. 안정 상태에서는 모든 상자가 변을 맞대고 이어져 있다. 즉 아무 상자에서 출발해 변을 공유하는 상자만 거쳐 다른 모든 상자에 갈 수 있다. 상자를 밀어서 연결이 끊어지면 위험 상태가 되고, 바로 다음 밀기로 다시 연결을 만들어야 한다.

아래 그림을 보자.

상자 4개가 모두 변을 맞대고 이어져 있으므로 안정 상태다. 여기서 가장 북쪽 상자를 서쪽으로 밀었다고 하자.

가장 북쪽 상자가 어떤 상자와도 닿지 않으므로 위험 상태다. 다음 밀기는 안정 상태로 되돌려야 한다. 그 상자를 남쪽으로 밀면 된다.

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

EZ-소코반 퍼즐은 판, 상자의 처음 배치, 상자가 마지막에 놓여야 하는 배치로 이루어진다. 상자를 미는 횟수가 가장 적은 해를 구하거나, 풀 수 없다고 판단하라. 처음 배치와 마지막 배치는 위험 상태가 아니다.

문제를 간단히 하려고, 창고지기인 당신은 언제든 판의 빈 칸 아무 곳으로나 뛰어갈 수 있다.

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

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

• .은 빈 칸
• #은 벽
• x는 마지막에 상자가 놓여야 하는 목표 칸
• o는 상자
• w는 목표 칸에 이미 놓인 상자

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

제한:

• $1 \le T \le 50$
• $1 \le R, C \le 12$
• 상자의 개수는 $1$개 이상 $5$개 이하

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

Case #X: K

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