Зняття нафти з поверхні
Завдяки певній компанії з "зелених" ресурсів з'явилася нова прибуткова галузь збору нафти. У Мексиканській затоці плавають великі плями сирої нафти, які чекають, щоб їх зібрали підприємливі нафтові барони. Один з таких нафтових баронів має спеціальний літак, що може знімати нафту з поверхні води. Однак, кожен знімок покриває прямокутник розміром 10м на 20м (орієнтований або зі сходу на захід, або з півночі на південь). Також вимагається, щоб прямокутник був повністю покритий нафтою, інакше продукт забруднюється чистою океанською водою і стає неприбутковим! Маючи карту нафтової плями, нафтовий барон хоче, щоб ви обчислили максимальну кількість знімків, які можна зробити. Карта є N×N сіткою, де кожна клітинка представляє 10м квадрат води, і кожна клітинка позначена як покрита нафтою або чистою водою.
Вхідні дані
Вхід починається з цілого числа K (1 ≤ K ≤ 100), що вказує кількість випадків. Кожен випадок починається з цілого числа N (1 ≤ N ≤ 600), що вказує розмір квадратної сітки. Кожен з наступних N рядків містить N символів, що представляють клітинки рядка на сітці. Символ '#' представляє нафтову клітинку, а символ '.' представляє клітинку з чистою водою.
Вихідні дані
Для кожного випадку слід вивести один рядок, відформатований точно так: "Case X: M", де X — це номер випадку (починаючи з 1), а M — максимальна кількість знімків нафти, які можна зробити.