3316 -- Snakes on a Plane

Language:

Snakes on a Plane

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 1357		Accepted: 515

Description

Assume we have an n × m grid of squares, each filled with either 0 or 1. A snake is a connected sequence of grid squares which has the following properties:

Each snake square has a 1 in it
Each snake square touches exactly two other snake squares (north/south/east/west), except the first and last square in the sequence (the head and tail of the snake)

A maximal snake is one in which we cannot add a 1 to either end without either lengthening the snake, combining two snakes together, or violating rule 2 above. The examples below show grids with and without maximal snakes (all empty squares have 0's in them). Notice that the second grid does not have a maximal snake since you can add a 1 at the end of either snake to get a larger snake.

For this problem, you will be given grids and must count the number of maximal snakes in each.

Input

Input will consist of multiple test cases. The first line of each test case will contain two positive integers n m indicating the number of rows and columns in the grid (the maximum value of each will be 200). The next n lines will consist of m characters (either '0' or '1') specifying the grid. The last case is followed by a line containing 0 0 which indicates end-of-input and should not be processed.

Output

For each test case, output a single line containing the number of maximal snakes in the grid.

Sample Input

Sample Output

1
0
3

Source

East Central North America 2006