Description

在使用 Google 街景时，你可能曾经拖动并放下过角色 Pegman。今天，一个调皮的用户要把 Pegman 放在一个 $R$ 行 $C$ 列的单位格矩形网格中的某个格子里。这个网格中的每个格子可能是空白的，也可能标有一个箭头，箭头指向四个可能的方向之一：上、右、下或左。

当 Pegman 被放在一个格子上时，如果该格子是空白的，Pegman 会永远静止不动。然而，如果该格子上有一个箭头，Pegman 会开始朝那个方向行走。在行走过程中，每当他遇到空白格子时，他会继续保持当前方向前进；但每当他遇到另一个箭头时，他会转向该箭头指示的方向，然后继续行走。

你知道 Pegman 可能会一直在网格上快乐地循环行走，但也有可能 Pegman 会走出网格的边界！你可以通过改变一个或多个箭头的方向来防止这种情况发生，从而拯救他。（每个箭头的方向只能更改为另外三种可能的方向；只能更改箭头，不能添加或移除箭头。）

你需要求出，最少需要更改多少个箭头的方向，才能确保无论 Pegman 最初被放在网格的哪个位置，他都不会走出网格边界？如果无论怎么更改箭头都无法保证这一点，则输出 IMPOSSIBLE。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为两个用空格分隔的整数 $R$ 和 $C$。接下来有 $R$ 行，每行有 $C$ 个字符，描述网格的每个格子，每个字符为以下之一：

. 句点 = 无箭头
^ 上箭头
> 右箭头
v 下箭头
< 左箭头

Output Format

对于每组测试数据，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最少需要更改的箭头数量，或者如果无论如何都无法保证 Pegman 不会走出网格，则输出 IMPOSSIBLE。

4
2 1
^
^
2 2
>v
^<
3 3
...
.^.
...
1 1
.

Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 0

Hint

样例解释

在第 1 组样例中，无论 Pegman 被放在哪里，他都一定会走出网格的上边界。你可以通过将最上面的箭头改为向下，从而让 Pegman 在这两个箭头之间来回循环，避免走出网格。

在第 2 组样例中，无论 Pegman 被放在哪里，他都会顺时针绕着网格循环行走，无需更改任何箭头。

在第 3 组样例中，调皮的用户可能会把 Pegman 放在网格中央的上箭头上，这样他会开始行走并最终走出网格的上边界。更改这个箭头的方向也无济于事：他只会从别的边界走出去。

在第 4 组样例中，唯一的起始格子是空白格，Pegman 会永远静止，不会有危险。

数据范围

• $1 \leq T \leq 100$。

小数据集（5 分）

• 时间限制：5 秒。
• $1 \leq R, C \leq 4$。

大数据集（10 分）

• 时间限制：10 秒。
• $1 \leq R, C \leq 100$。

由 ChatGPT 4.1 翻译