Number of Islands

Medium

You are given an m x n binary grid where 1 means land and 0 means water. Count how many connected islands exist. Cells connect only up, down, left, and right.

Input Format

Line 1: m n
Next m lines: each line is a binary string of length n

Output Format

Print one integer: the number of islands.

Constraints

1 <= m, n <= 120
grid[i][j] is 0 or 1

Examples

Input

Output

Explanation

All land cells connect to form one island.

Input

Output

Explanation

There are three disconnected components of land.

Hints

Hint 1

Hint 2

Code

Upload

Input

Expected Output

All land cells connect to form one island.

Run uses the currently selected testcase. Submit always evaluates your code against the full hidden test suite from the database.