시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2 2 2 100.000%

문제

Troy loves triangles. He especially likes counting triangles. He has an N-by-N grid consisting of either “.” or “#” characters. Help him count the number of triangles formed only by “#” characters in the grid. Triangles are of the form

          #
    #    ### 
#, ###, #####, etc.

More formally, a triangle of height h consists of h rows for some positive integer h. The ith row contains 2i − 1 “#” characters for i = 1, . . . , h. The rows are centred above each other so that they are symmetrical about a vertical line down their middle.

입력

The first line contains the number N (1 ≤ N ≤ 2000) representing the size of the grid. The next N lines each contain N characters as described above.

출력

Output the number of triangles in the grid.

예제 입력 1

5
.....
.###.
.###.
#####
.....

예제 출력 1

16