---
# System prepended metadata

title: Untitled

---

## MÊ CUNG CỜ CARO

Cô bò Bessie thích chơi với mê cung. Cô ấy cũng thích chơi Cờ Caro (hay đúng hơn là một loại Cờ Caro của bò, sẽ giải thích kĩ sau). Bác John đã nghĩ ra một trò chơi mới để cùng lúc kết hợp cả hai.

Trước hết, Cờ Caro phiên bản bò, thay vì đánh dấu các kí tự 'X' và 'O' lên một bảng vuông $3\times3$, bò lại đánh dấu 'M' và 'O' lên bảng đó. Trong mỗi lượt đi, mỗi chú bò đánh dấu 'M' hoặc 'O' lên bất cứ ô nào còn trống (khác với chúng ta khi một người chơi chỉ đánh dấu 'X' và người còn lại đánh dấu 'O'). Chú bò nào có thể tạo thành chuỗi 'MOO' trước, bât kể ngang, dọc, chéo, sẽ chiến thắng. Thứ tự ngược lại cũng được chấp nhận, hay nói cách khác, việc tạo thành chuỗi 'OOM' cũng tương đương. Như Cờ Caro truyền thống, trường hợp hòa có thể xảy ra. Mỗi nước đi của trò chơi được đặc trưng bởi 3 kí tự, 'Mij' hoặc 'Oij', với _i_, _j_ trong khoảng 1...3, tượng trưng cho một dấu 'O' hay 'M' được đánh ở hàng _i_ và cột _j_.

Để thách thức Bessie, bác John đã tạo ra một mê cung vuông có dạng lưới ô vuông *N* $\times$ *N* ($3 \le$ _N_ $\le 25$). Một số ô, bao gồm cả các ô ở biên, có những đống cỏ khô lớn mà Bessie không thể đi qua. Bessie có thể tự do di chuyển trong những ô trống còn lại trong mê cung, theo bốn hướng Đông, Tây, Nam và Bắc. Vài ô sẽ chứa một mảnh giấy biểu tượng cho một nước đi trong môn "Cờ Caro Bò". Khi di chuyển qua cá ô có mảnh giấy, Bessie buộc phải làm theo nước đi ghi sẵn trên đó, nếu ô mà nước đi muốn đánh dấu vào còn trống. Bessie không có đối thủ trong trò chơi này, nhưng những ô bị chặn bởi đống cổ khô sẽ ngăn cô hoàn thành chuỗi 'MOO'.

Biết rằng Bessie sẽ kết thúc trò chơi ngay khi giành chiến thắng, xác định số trạng chiến thắng mà cô có thể tạo ra bằng cách di chuyển trong mê cung.

#### INPUT(Dữ liệu từ Terminal/Stdin):

Dòng đầu tiên chứa số nguyên _N_.

Mê cung được mô tả trong n dòng tiếp theo, mỗi dòng chứa 3*N* kí tự, 3 kí tự biểu diễn cho một ô vuông, với '###' là ô bị chắn, '...' là ô trống, 'BBB' với ô mà Bessie đang đứng, và một bộ kí hiệu cho một nước đi mà Bessie phải thực hiện nếu đi vào. Dữ liệu đảm bảo có duy nhất một ô 'BBB'.

#### OUTPUT(Dữ liệu tới Terminal/Stdout):

In ra một số nguyên duy nhất là số trạng thái chiến thắng Bessie có thể đạt được (có thể là 0) bằng cách di chuyển trong mê cung và dừng lại ngay khi chiến thắng.

#### SAMPLE INPUT:

```
7

#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################
```

#### SAMPLE OUTPUT:

```
8
```

Trong ví dụ, có 8 trạng thái chiến thắng cuối cùng có thể đạt được:

```
O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM
```

Để giải thích kĩ hơn, ta chú ý vào một trong các trạng thái trên:

```
O..
...
OOM
```

Ở đây, Bessie đến ô O11, sau đó đi xuống phía dưới và đi qua các ô O32, M33, O31. Trò chơi sau đó kết thúc, bởi cô đã thắng(hay nói cách khác cô ta không thể đi tiếp đến ô M11 ở phía Bắc vị trí đứng hiện tại).