### Snakes on a Plane

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem 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:

1. Each snake square has a 1 in it

2. 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.

1. Each snake square has a 1 in it

2. 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

7 10 1111111110 0000000010 1100000011 1011110001 1010010001 1010010111 1110011100 7 10 1111111110 0000000010 0001010011 1011010001 1010010001 1010010111 1110011100 7 10 1011111110 0100000010 1101011011 1011010001 1010010001 1010010111 1110011100 0 0

#### Sample Output

1 0 3

#### Hint

#### Source

The 2006 ACM-ICPC East Central North America