Problem: There are some coins in the xy-plane. The positions of the coins are represented by a grid of characters with H rows and W columns. If the character at the i-th row and j-th column, s_{ij}, is `#`, there is one coin at point (i,j); if that character is `.`, there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold. There is also no coin at point (x,y) where x or y (or both) is not an integer. Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

* Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.



Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|. Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

* 1 \leq H,W \leq 300
* s_{ij} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}


Output

Print the number of triples that satisfy the condition.

Examples

Input

5 4
#.##
.##.
#...
..##
...#


Output

3


Input

5 4
.##
.##.
...
..##
...#


Output

3


Input

13 27
......#.........#.......#..
...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
.#.#.#...###..
...........#...#...#######
..#######..#...#...#.....#
..#.....#..#...#...#.###.#
..#######..#...#...#.#.#.#
..........##...#...#.#####


Output

870

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define int long long

#define TASKNAME ""

using namespace std;
const int K = 300;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<bitset<K> > v;
    for (int i=0; i < n; i ++){
        string s;
        cin >> s;
        bitset<K> b;
        for (int j=0; j < m; j++){
            if (s[j] == '#') b[j] = 1;
        }
        v.push_back(b);
    }
    int ans = 0;
    bitset<K> a, b, c;
    for (int i=0; i < n; i++){
        for (int j=i; j < n; j++){
            for (int k=j; k < n; k++){
                if (i==k) continue;
                a = v[i], b = v[j], c = v[k];
                int d1 = j-i, d2 = k-j, s1, s2;
                if (d1 >= d2) s1 = d1, s2=2*d1-d2;
                else s1 = d1 + 2*(d2-d1), s2 = d2;
                //cout << i << " " << j << " " << k << " " << s1 << " " << s2 << endl;
                a <<= s1, c <<= s2;
                b &= a;
                b &= c;
                ans += b.count();
                if (d1==0 || d2==0) continue;
                a = v[i], b = v[j], c = v[k];
               // cout << a[1] << " " << s1 << endl;
                a >>= s1, c >>= s2;
                b &= a;
                b &= c;
                ans += b.count();
            }
        }
    }
    cout << ans;

}