페그맨

구글 스트리트 뷰를 쓰다가 페그맨 아이콘을 집어 지도 위에 내려놓아 본 적이 있을 것이다. 오늘은 장난기 많은 사용자가 $R$행 $C$열 격자의 한 칸에 페그맨을 내려놓으려고 한다. 격자의 각 칸은 비어 있거나, 위, 오른쪽, 아래, 왼쪽 중 한 방향을 가리키는 화살표가 그려져 있다.

페그맨을 내려놓은 칸이 비어 있으면 페그맨은 그 자리에 영원히 서 있는다. 화살표가 있으면 그 방향으로 걷기 시작한다. 걷다가 빈 칸을 만나면 가던 방향을 그대로 유지하고, 다른 화살표를 만나면 그 화살표의 방향으로 바꿔서 계속 걷는다.

페그맨이 격자 안을 영원히 돌아다닐 수도 있지만, 격자 밖으로 걸어 나가 버릴 수도 있다. 화살표를 하나 이상 다른 방향으로 바꾸면 이를 막을 수 있다. 화살표의 방향은 나머지 세 방향 중 하나로만 바꿀 수 있고, 화살표를 새로 그리거나 지울 수는 없다.

페그맨을 격자의 어느 칸에 내려놓아도 격자 밖으로 나가지 않게 하려면, 방향을 바꿔야 하는 화살표는 최소 몇 개인가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 $R$, $C$가 주어진다. 이어지는 $R$개의 줄에는 각각 $C$개의 문자가 주어지고, 각 문자는 한 칸을 다음과 같이 나타낸다.

• . 마침표: 화살표 없음
• ^ 위쪽 화살표
• > 오른쪽 화살표
• v 아래쪽 화살표
• < 왼쪽 화살표

제한

• $1 \le T \le 100$
• $1 \le R, C \le 100$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 페그맨을 어느 칸에 내려놓아도 격자를 벗어나지 않게 만들기 위해 방향을 바꿔야 하는 화살표의 최소 개수이다. 화살표를 몇 개 바꾸더라도 그렇게 만들 수 없으면 y 자리에 IMPOSSIBLE을 출력한다.

첫 번째 예제의 첫 번째 테스트 케이스에서는 페그맨을 어디에 내려놓아도 위쪽 경계 밖으로 나간다. 위에 있는 화살표를 아래쪽으로 바꾸면 두 화살표 사이를 영원히 오가므로 막을 수 있다.

두 번째 테스트 케이스에서는 어디에 내려놓아도 격자를 시계 방향으로 계속 돈다. 바꿔야 할 화살표가 없다.

세 번째 테스트 케이스에서는 사용자가 가운데 위쪽 화살표 칸에 페그맨을 내려놓을 수 있고, 그러면 위쪽 경계 밖으로 나간다. 이 화살표의 방향을 바꿔도 다른 경계로 나갈 뿐이라 소용이 없다.

네 번째 테스트 케이스에서는 내려놓을 수 있는 칸이 빈 칸 하나뿐이라 페그맨은 그대로 서 있는다.