Vốn luôn nổi tiếng là người am hiểu công nghệ, Farmer John đang thử nghiệm chiếc máy ảnh định vị bò tự động mới gắn trên máy bay không người lái. Thiết bị này được cho là có thể chụp ảnh cánh đồng rồi tự động xác định vị trí của các con bò. Tiếc rằng máy ảnh không được trang bị một thuật toán tìm bò đủ tốt, vì vậy FJ cần bạn giúp phát triển một thuật toán tốt hơn.

Ảnh chụp từ trên cao trang trại của ông được mô tả bởi một lưới ký tự \(N \times N\), trong đó mỗi ký tự thuộc khoảng \(A \ldots Z\) và biểu thị một trong \(26\) màu có thể có. Farmer John cho rằng cách tốt nhất để định nghĩa một vị trí có thể có bò (PCL) là như sau: PCL là một lưới con hình chữ nhật (có thể là toàn bộ ảnh), có các cạnh song song với các cạnh của ảnh và không nằm trong bất kỳ PCL nào khác (do đó, không có lưới con nhỏ hơn của một PCL cũng là PCL). Ngoài ra, PCL phải thỏa mãn tính chất sau: nếu chỉ xét nội dung bên trong hình chữ nhật và bỏ qua phần còn lại của ảnh, phải có đúng hai màu; một màu tạo thành một vùng liên thông, còn màu kia tạo thành từ hai vùng liên thông trở lên.

Chẳng hạn, một hình chữ nhật có nội dung

AAAAA
ABABA
AAABB

sẽ là một PCL vì các ký tự A tạo thành một vùng liên thông duy nhất còn các ký tự B tạo thành nhiều hơn một vùng liên thông. Cách diễn giải ở đây là một con bò màu A có các đốm màu B.

Một vùng được gọi là "liên thông" nếu ta có thể đi qua toàn bộ vùng bằng cách liên tục di chuyển từ một ô trong vùng sang một ô khác trong vùng theo các bước lên, xuống, trái hoặc phải.

Cho ảnh do máy ảnh của FJ trả về, hãy đếm số PCL.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), kích thước của lưới (\(1 \leq N \leq 20\)). \(N\) dòng tiếp theo mô tả ảnh, mỗi dòng gồm \(N\) ký tự.

Dữ liệu ra

In số PCL trong ảnh.

Ví dụ

4
ABBC
BBBC
AABB
ABBC

2

ABB
BBB
AAB
ABB

BC
BC
BB
BC

Nguồn

USACO 2017 US Open Contest, Silver — Where's Bessie? Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=740