Aurora Patterns

Santa has returned to the North Pole Christmas zone and it is almost midnight. The spectacular artificial aurora show is about to begin. Unlike the natural auroras of polar regions, these are man-made displays hosted by Santa. Each display is an n × m dot matrix where each dot (or cell) is either lit or unlit. The lit dots form a beautiful pattern composed of several sub-patterns.

Santa defines a sub-pattern as follows: for any two lit points A(x₁, y₁) and B(x₂, y₂) in the grid, if their Manhattan distance satisfies $$ |x_1 - x_2| + |y_1 - y_2| \leq 2, $$ then these two points belong to the same sub-pattern. Note that this relation is transitive; that is, if point P is connected to Q and Q is connected to R under this rule, then P, Q, and R are all part of the same sub-pattern.

Your task is to compute the number of distinct sub-patterns in a given aurora image.

inputFormat

The first line contains two integers n and m (the number of rows and columns of the grid, respectively). Each of the next n lines contains a string of length m consisting only of the characters '0' and '1', where '1' indicates a lit point and '0' indicates an unlit point.

outputFormat

Output a single integer representing the number of distinct sub-patterns (groups of lit points connected via Manhattan distance at most 2) in the grid.

sample

3 3
010
111
010

1