Pegman

Google 스트리트 뷰를 사용하면서 Pegman 캐릭터를 집어 들었다가 내려놓아 본 적이 있을 것이다. 오늘은 장난기 많은 사용자가 R개의 행과 C개의 열로 이루어진 단위 격자의 직사각형 격자 중 어떤 칸에 Pegman을 놓으려고 한다. 이 격자의 각 칸은 비어 있을 수도 있고, 위쪽, 오른쪽, 아래쪽, 왼쪽이라는 네 가지 가능한 방향 중 하나를 가리키는 화살표가 표시되어 있을 수도 있다.

Pegman을 격자 칸에 놓았을 때, 그 칸이 비어 있으면 Pegman은 영원히 가만히 서 있는다. 하지만 그 칸에 화살표가 있으면 Pegman은 그 방향으로 걷기 시작한다. 걸어가는 동안 빈 칸을 만날 때마다 현재 방향으로 계속 걸어가지만, 다른 화살표를 만날 때마다 그 화살표가 가리키는 방향으로 바꾼 뒤 계속 걸어간다.

Pegman이 즐겁게 격자를 빙빙 돌며 영원히 계속 걸을 수도 있지만, Pegman이 걷다가 격자의 가장자리 밖으로 나갈 수도 있다! 하나 이상의 화살표 방향을 바꾸어 이를 막고 Pegman을 구할 수 있을지도 모른다. (각 화살표의 방향은 나머지 세 가지 가능한 방향 중 하나로만 바꿀 수 있으며, 화살표는 변경만 할 수 있고 추가하거나 제거할 수는 없다.)

Pegman이 처음 격자의 어디에 놓이더라도 가장자리 밖으로 걸어 나가지 않도록 하기 위해 방향을 바꿔야 하는 화살표의 최소 개수는 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 240초. 1 ≤ R, C ≤ 4.

큰 데이터 세트

시간 제한: 480초. 1 ≤ R, C ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 R, C가 있는 한 줄로 시작한다. 그다음에는 각각 C개의 문자로 이루어진 R개의 줄이 주어지며, 각 문자는 격자의 한 칸을 나타내고 다음 중 하나이다:

` . 마침표 = 화살표 없음 ^ 캐럿 = 위쪽 화살표

초과 기호 = 오른쪽 화살표 v 소문자 v = 아래쪽 화살표 < 미만 기호 = 왼쪽 화살표 `

각 테스트 케이스마다 "Case #x: y"을 담은 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 Pegman이 처음 어디에 놓이더라도 격자를 벗어나지 않도록 하기 위해 변경해야 하는 화살표의 최소 개수이다. 화살표를 아무리 많이 변경해도 이를 보장할 수 없다면 IMPOSSIBLE이라는 문자열을 출력한다.

케이스 #1에서는 Pegman을 어디에 놓더라도 격자의 위쪽 가장자리 밖으로 걸어 나가는 것이 확실하다. 가장 위쪽 화살표가 아래쪽을 가리키도록 변경하면 이를 막을 수 있으며, 그러면 Pegman은 두 화살표 사이를 영원히 앞뒤로 걸어 다니게 된다.

케이스 #2에서는 Pegman을 어디에 놓더라도 보드를 시계 방향으로 원을 그리며 빙빙 돌게 된다. 변경해야 할 화살표는 없다.

케이스 #3에서는 장난기 많은 사용자가 Pegman을 격자 중앙의 위쪽 화살표 위에 놓을 수도 있으며, 이 경우 Pegman은 걷기 시작한 뒤 격자의 위쪽 가장자리 밖으로 걸어 나간다. 이 화살표의 방향을 변경해도 도움이 되지 않는다. 단지 다른 가장자리 밖으로 걸어 나가게 될 뿐이다.

케이스 #4에서는 가능한 유일한 시작 칸이 비어 있으므로 Pegman은 영원히 가만히 서 있고 아무런 위험도 없다.