페그맨 (작은 입력)

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

페그맨을 빈 칸에 내려놓으면 그 자리에 영원히 서 있는다. 화살표가 있는 칸에 내려놓으면 그 방향으로 걷기 시작한다. 걷다가 빈 칸을 지날 때는 가던 방향을 그대로 유지하고, 화살표가 있는 칸에 들어서면 그 화살표의 방향으로 방향을 바꾼 뒤 계속 걷는다.

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

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

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

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

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 페그맨을 어느 칸에 놓더라도 격자 밖으로 나가지 않게 만드는 데 필요한 최소 화살표 변경 개수이다. 화살표를 아무리 바꿔도 그렇게 만들 수 없으면 $y$ 자리에 IMPOSSIBLE을 출력한다.

첫 번째 예제의 케이스 1에서는 페그맨을 어느 칸에 놓아도 위쪽 모서리로 걸어 나간다. 위에 있는 화살표를 아래쪽으로 바꾸면 두 화살표 사이를 영원히 오간다.

케이스 2에서는 어느 칸에 놓아도 시계 방향으로 격자를 계속 돈다. 바꿀 화살표가 없다.

케이스 3에서는 짓궂은 사용자가 가운데의 위쪽 화살표에 페그맨을 놓을 수 있고, 그러면 페그맨은 위쪽 모서리로 걸어 나간다. 이 화살표의 방향을 바꿔도 다른 모서리로 나갈 뿐이다.

케이스 4에서는 놓을 수 있는 칸이 빈 칸 하나뿐이므로 페그맨은 가만히 서 있고 위험하지 않다.