Đồng cỏ của Farmer John có thể được biểu diễn bằng một lưới ô vuông \(N\times N\) (\(1\le N\le 300\)), gồm các vị trí \((i,j)\) với mọi \(1\le i,j\le N\). Với mỗi ô vuông của lưới, ký tự tương ứng trong dữ liệu vào là * nếu có đúng một con bò tại vị trí đó, và là . nếu không có con bò nào tại đó.

FJ tin rằng vẻ đẹp của đồng cỏ tỉ lệ thuận với số bộ ba con bò có vị trí cách đều nhau. Nói cách khác, chúng tạo thành một tam giác đều. Không may, chỉ mới gần đây FJ nhận ra rằng vì tất cả bò của ông đều nằm tại các tọa độ nguyên, không thể tồn tại bất kỳ bộ ba đẹp nào nếu sử dụng khoảng cách Euclid! Do đó, FJ quyết định chuyển sang sử dụng khoảng cách "Manhattan". Một cách chính thức, khoảng cách Manhattan giữa hai vị trí \((x_0,y_0)\) và \((x_1,y_1)\) bằng \(|x_0-x_1|+|y_0-y_1|\).

Cho lưới biểu diễn vị trí của các con bò, hãy tính số bộ ba cách đều.

Phân nhóm

Ngoài ví dụ, có mười bốn test, mỗi test ứng với một giá trị trong dãy

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Với mỗi \(1\le i\le N\), dòng thứ \(i+1\) của dữ liệu vào chứa một xâu độ dài \(N\) chỉ gồm các ký tự * và .. Ký tự thứ \(j\) cho biết có một con bò tại vị trí \((i,j)\) hay không.

Dữ liệu ra

In một số nguyên duy nhất là đáp án. Có thể chứng minh rằng đáp án nằm trong phạm vi của số nguyên 32 bit có dấu.

Ví dụ

3
*..
.*.
*..

1

Nguồn

USACO 2020 February Contest, Platinum - Equilateral Triangles: https://usaco.org/index.php?page=viewproblem2&cpid=1021

Tác giả: Benjamin Qi.