Pollution! Pollution! There have been oil spills in the ocean!

Jeffrey the sailor wants to sail across the Atlantic ocean, but he doesn't want to get his boat dirty, so he must avoid the oil patches at all cost!

The Atlantic ocean can be modelled as an ~N~ by ~N~ grid, where each cell is either originally O, an oil patch, ., a patch of empty water, or X, a wall that oil cannot spread to. Each second, a patch of oil spreads in each cardinal direction, if that location does not already have a patch of oil.

This is how a patch of oil would spread in the first 2 seconds.

.....                    .....                    ..O..
.....                    ..O..                    .OOO.
..O..                    .OOO.                    OOOOO
.....                    ..O..                    .OOO.
.....                    .....                    ..O..

For his curiosity, Jeffrey would like to see at each point in time, from ~0~ to ~N^2~, how many distinct patches of oil there are. As in, how many patches of oil are there such that you can visit all other patches of oil in that group, while not being able to reach any patch of oil outside this group.

Input Specification

The first line of input will contain ~N~, the size of the grid.

The next ~N~ lines will contain ~N~ characters, representing each tile of the grid.

Output Specification

Output ~N^2+1~ lines, each representing the number of oil patches remain.

Constraints

For all subtasks, ~1 \le N \le 1000~

Subtask 1 [10%]

~1 \le N \le 20~

Subtask 2 [90%]

No additional constraints.

Sample Input 1

3
O..
...
..O

Sample Output 1

2
2
1
1
1
1
1
1
1
1

Explanation for Sample Input 1

This is how the oil spreads.

O..                      OO.                      OOO
...                      O.O                      OOO
..O                      .OO                      OOO

Note that after second 2, the ocean become static since the entire ocean is filled.

Sample Input 2

5
OX...
OX.X.
.X.X.
.X.X.
...XO

Sample Output 2

2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Explanation for Sample Input 2

Notice that the 2 top oil patches initially start as one patch. After 7 seconds, the two patches merge to become one.