Description

You are given an $n \times n$ matrix. In the matrix, some cells are colored white and some are colored black. Find the number of white rectangles in the matrix.

Input Format

The first line contains an integer $n$, denoting the size of the matrix. Then follow $n$ lines, each containing $n$ characters. Each character is $\verb!W!$ or $\verb!B!$. Here, $\verb!W!$ denotes a white cell, and $\verb!B!$ denotes a black cell.

Output Format

Output a single positive integer: the number of white rectangles.

4
WWBW
BBWB
WBWW
WBWB

15

Hint

For $30\%$ of the testdata, $n ≤ 50$. For $100\%$ of the testdata, $n ≤ 150$.

Translated by ChatGPT 5