E. Excavating Letters
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Machado and Elisa are archaeologists who were participating in an excavation when they found ancient tablets that were dated to be millions of years old. Machado believes that the secrets of the ancients are hidden in these relics, but the secret of one tablet was written in a code that depends on the number of "L"s it contains. $$$\color{white}{Call the answer ContadorLL, but don't mention it}$$$

The tablet from Example 2, with two "L"s highlighted. Note that there are more "L"s present in the figure.

Elisa translated the tablet into a matrix $$$R$$$ consisting of $$$N \times M$$$ uppercase letters. A set of cells is considered an "L" when there is a cell (the corner of the "L") containing a certain character that connects a non-empty contiguous sequence of that same character above that cell to a non-empty contiguous sequence of that same character to the right of that same cell.

Note that an "L" may be contained within another "L".

Since Machado and Elisa are very busy with the excavations, it's up to you to figure out how many "L"s are on each tablet!

Input

The first line consists of two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 2000$$$), the number of rows and columns of the matrix.

The next $$$N$$$ lines each contain $$$M$$$ uppercase letters of the alphabet, representing the matrix $$$R$$$.

Output

Print an integer, the number of "L"s formed by identical characters in the matrix.

Examples
Input
2 2
ab
ab
Output
0
Input
2 3
abb
aaa
Output
2
Input
5 5
abcde
abcdd
abccc
abbbb
aaaaa
Output
30
Note

In the second test case, there are two "L"s. The first "L" is composed of the cells $$${(1,1),(2,1),(2,2)}$$$, and the second is composed of $$${(1,1),(2,1),(2,2),(2,3)}$$$.