You are playing a game in which you have a rectangular grid of n*n cells. Each cell is either empty or has a firework. Empty cells are marked with ".", cells with firework are marked with "*" . Two cells are said to be adjacent if they share a side.
If firework in any cell explodes it destroys itself and the empty cells connected to it. Two cells are connected if there is a path of empty adjacent cells between them.
You have to find the number of cells that will be destroyed if the fireworks are triggered independently.
Input Format:
The first line contains an integer n denoting the dimensions of the grid.
Each of the next n lines contains symbols: "." for empty cells, "*" for cells containing a firework.
Note: All rows have n number of symbols.
Output Format:
Print the sum of the number of cells destroyed if each bomb is triggered independently.
Input Constraints:
1≤n≤1000
Here n = 4. So given grid A is of 4×4 size.
Considering indexing starts from 1 in the grid:
1) A[1][1] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total.
2) A[1][4] has firework , so it will destroy all the 9 empty cells connected to it and including itself, it will destroy 10 cells in total.
3) A[2][3] has firework , so it will destroy all the 9 empty cells connected to it and including itself, it will destroy 10 cells in total.
4) A[3][1] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total.
5) A[3][4] has firework , so it will destroy all the 9 empty cells connected to it and including itself, it will destroy 10 cells in total.
6) A[4][1] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total.
7) A[4][4] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total.
So total cells destroyed will be 9+10+10+9+10+9+9 = 66.
