Khi sử dụng Google Street View, có lẽ bạn từng nhấc nhân vật Pegman lên rồi thả xuống. Hôm nay, một người dùng tinh nghịch sẽ đặt Pegman vào một ô nào đó của lưới chữ nhật gồm các ô vuông đơn vị, có \(R\) hàng và \(C\) cột. Mỗi ô có thể trống hoặc mang một mũi tên chỉ theo một trong bốn hướng: lên, phải, xuống hoặc trái.

Khi Pegman được đặt vào một ô, nếu ô đó trống thì anh ấy đứng yên mãi mãi. Nếu ô có mũi tên, Pegman bắt đầu đi theo hướng mũi tên. Trong lúc đi, khi gặp một ô trống, anh ấy tiếp tục đi theo hướng hiện tại; khi gặp một mũi tên khác, anh ấy đổi sang hướng của mũi tên đó rồi tiếp tục đi.

Pegman có thể vui vẻ đi vòng quanh lưới mãi mãi, nhưng cũng có thể bước ra ngoài biên lưới. Bạn có thể ngăn điều đó và cứu anh ấy bằng cách đổi hướng của một hoặc nhiều mũi tên. Mỗi mũi tên chỉ được đổi sang một trong ba hướng còn lại; chỉ được đổi hướng, không được thêm hoặc xóa mũi tên.

Hãy tìm số mũi tên ít nhất cần đổi để bảo đảm Pegman không rời khỏi lưới, bất kể ban đầu anh ấy được đặt ở đâu.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(R\), \(C\) cách nhau bởi dấu cách. Sau đó là \(R\) dòng, mỗi dòng có \(C\) ký tự mô tả các ô:

• .: ô không có mũi tên;
• ^: mũi tên lên;
• >: mũi tên sang phải;
• v: mũi tên xuống;
• <: mũi tên sang trái.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số mũi tên ít nhất phải đổi để Pegman không rời lưới, bất kể vị trí ban đầu. Nếu không thể bảo đảm điều đó dù đổi bao nhiêu mũi tên, in IMPOSSIBLE.

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Tập nhỏ: \(1\le R,C\le4\).
• Tập lớn: \(1\le R,C\le100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

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

Nguồn

Google Code Jam 2015, Vòng 2, bài Pegman.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.