Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT013G - BÀI G - TRÒ CHƠI PIKACHU

Cho một bảng hình chữ nhật kích thước m×n ô vuông kích thước đơn vị. Các dòng được đánh số từ 1 đến m, từ trên xuống dưới. Các cột được đánh số từ 1 đến n, từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của bảng được gọi là ô (i,j). Mỗi ô của bảng hoặc được để trống hoặc chứa một ký tự chữ cái la tinh in hoa từ A đến Z. Hai ô chứa cùng một ký tự giống nhau có thể xoá được nếu tâm (giao điểm của hai đường chéo) của 2 ô này có  thể nối với nhau bằng một đường gấp khúc gồm không quá 3 đoạn thẳng độ dài nguyên, mỗi đoạn song song với cạnh của bảng, và ngoại trừ hai ô cần xoá, đường gấp khúc này chỉ qua các ô trống hay nằm ngoài bảng.

Nhiệm vụ của bạn là viết một chương trình đọc hai số m, n và m xâu độ dài n mô tả các dòng của bảng để đếm số cặp ô mà có thể xóa được.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.
 
Mỗi bộ dữ liệu gồm một nhóm dòng có khuôn dạng:
  Dòng đầu tiên chứa 2 số nguyên m, n (m,n ≤ 100);
  Dòng thứ i +1 chứa xâu n ký tự mô tả dòng thứ i của bảng (i = 1, 2, ..., m). Các ô trống được thể hiện bằng dấu chấm "."

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng một số là số cặp ô mà có thể xóa được.

Example

Input:
1 
2 3
AA.
CCA
Output:
4

Được gửi lên bởi:adm
Ngày:2013-04-01
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.