Rainforest Canopy

A tropical rainforest is usually divided into four layers: the emergent layer, the canopy layer, the understory, and the forest floor. Telling the emergent layer apart from the canopy layer is the hard part. The emergent layer holds only a few very large trees that grow above the general canopy and reach heights of 45 to 55 metres. The canopy layer is 30 to 45 metres tall and holds more species than any other layer of the rainforest. With biodiversity in crisis, the Whole Forest Observatory monitors rainforest canopy and looks for suitable canopy research sites.

A group of engineers found a simple satellite imagery technique that marks canopy layers on a spot image of a wide rainforest area. The spot image is a square and is stored as pixels, small cells that each hold a 1 or a 0. One pixel describes one region of area $1\,\text{km}^2$. A pixel is 1 when part or all of its region is canopy layer, and 0 otherwise.

The following assumptions hold.

• A canopy layer is represented by at least one 1.
• Two pixels holding a 1 touch when their row numbers differ by at most 1 and their column numbers differ by at most 1, and pixels that touch belong to the same canopy layer. All eight neighbours around a pixel count, diagonals included. An image whose pixels are all 1 is a single large canopy layer.
• Distinct canopy layers do not touch one another.
• There is no wrap-around. The bottom row is not adjacent to the top row, and the leftmost column is not adjacent to the rightmost column.

Write a program that reads spot images and counts the canopy layers in each image.

The input consists of up to 1000 test cases and ends at end of file. Each test case starts on a new line with a positive integer $N$ ($1 \le N \le 40$), the side length of the image. The next $N$ lines give the pixels of the image, each line holding $N$ characters that are either 0 or 1. An image may hold no 1 at all, and such an image has no canopy layer.

For each test case print a single line. The line starts with Case #x: where x is the case number, counting from one, followed by a single space and then the number of canopy layers in that spot image.