Count Islands in a Grid

You are given a grid of size N × M where each cell is either open or blocked. An open cell is denoted by '1' and a blocked cell is denoted by '0'. Two open cells are considered connected if they are adjacent horizontally or vertically (diagonal connectivity is not considered). An island is defined as a maximal set of connected open cells. Your task is to determine the number of distinct islands in the grid.

In mathematical terms, an island can be described as a set of cells satisfying

[ I = { (i,j) \mid grid[i][j] = 1 \text{ and } \forall (i', j') \in I, \text{ there exists a path of adjacent open cells connecting } (i, j) \text{ and } (i', j') } ]

You should read the grid from standard input and print the resulting island count to standard output.

inputFormat

The first line of input contains an integer N representing the number of rows in the grid. This is followed by N lines, each representing a row of the grid. Each row is a string consisting of characters '0' and '1', where '1' indicates an open cell and '0' indicates a blocked cell.

Example:

4
11000
11000
00100
00011

outputFormat

Output a single integer representing the number of islands in the grid.

Example:

3

## sample

4
11000
11000
00100
00011

3