Навес тропического леса
Тропический дождевой лес обычно делится на четыре основных слоя: верхний ярус, полог, подлесок и лесная подстилка. Из этих четырех слоев довольно сложно отличить верхний ярус от полога. Верхний ярус содержит небольшое количество очень больших деревьев, которые растут выше общего полога, достигая высоты от 45 до 55 метров. Полог является самым богатым слоем разнообразного дождевого леса и варьируется по высоте от 30 до 45 метров. Из-за кризиса биоразнообразия мониторинг полога дождевого леса является миссией Обсерватории Целого Леса, которая пытается определить подходящие места для исследований полога.
Группа инженеров разработала простую технику спутниковой съемки, которая может отмечать слои полога на снимке большой площади дождевого леса. Снимок представляет собой квадрат и хранится в виде пикселей, то есть маленьких ячеек, содержащих либо 1, либо 0. Каждый пиксель несет информацию о конкретном регионе площадью 1 км^2. Положение пикселя содержит 1, если часть или весь представленный регион является слоем полога, и 0 в противном случае.
Следующие предположения верны:
Слой полога представлен как минимум одной 1.
Ячейки с соседними сторонами на общем пикселе, содержащем 1, составляют слой полога. Изображение одного большого слоя полога будет содержать все 1.
Различные слои полога не касаются друг друга.
Нет обертывания, то есть пиксели внизу не соседствуют с верхними, а левые не соседствуют с правыми.
Напишите программу, которая считывает снимки и правильно подсчитывает количество слоев полога на этих снимках.
Входные данные
Входные данные состоят из до 1000 тестовых случаев. Каждый тестовый случай описывает снимок области дождевого леса, который начинается с новой строки с положительного целого числа N, (1 ≤ N ≤ 40), указывающего размерность изображения. Следующие N строк каждого тестового случая очерчивают пикселизированное представление изображения.
Выходные данные
Для каждого тестового случая выведите одну строку, начинающуюся с префикса "Case #x: ", где x представляет номер случая (начиная с единицы и увеличиваясь с каждым новым тестовым случаем), за которым следует один пробел и затем результат, то есть количество слоев полога на снимке.