e-olymp
Задачі

Ліва кнопка миші

Ліва кнопка миші

Мінер є досить популярною грою в операційній системі Windows. Мета гри полягає у пошуку мін і маркуванні їх положення. Ви розміщуєте клацанням правої кнопки миші невеличкий прапорець у клітинці, в якій на Вашу думку розміщена міна. Клацанням лівої кнопки миші можна відкрити клітинку, у якій на Вашу думку міни немає. Якщо у цьому квадраті все ж таки розміщена міна, то вона взривається і Ви програєте. У протилежному випадку є два варіанти. У першому випадку відкривається число від 1 до 8, яке показує сумарну кількість мін, що оточують дану клітинку. Наприклад, якщо Ви натиснули ліву кнопку миші і в квадраті висвітилось число 8, то це означає, що дана клітинка ооточена 8 клітинками з мінами, тобто всі 8 сусідніх клітинок містять міни. У другому випадку, якщо навколо цієї клітинки немає сусідніх мін, то крім цієї клітинки відкриваються і всі сусідні. Якщо в деяких з сусідніх клітинок також немає оточуючих мін, то процес відкриття сусідніх клітинок продовжується. Тобто фактично комп'ютер допомагає Вам відкрити всі вільні від мін сусідні клітинки. Мета гри полягає у відкритті всіх вільних від мін клітинок. Том дуже захоплюється цією грою, але, на жаль, його права кнопка миші пошкоджена і він може користуватись лише лівою кнопкою миші. Для того щоб уникгути можливого подальшоего пошкодження миші він хоче завершити гру натиснувши на ліву кнопку миші мінімальну кількість разів. Знаючи початкове положення у грі Вам необхідно визначити цю саму мінімальну кількість натиснень лівою кнопкою миші.

prb1092

Вхідні дані

Перший рядок містить ціле число, яке вказує кількість тестових випадків T (T12). Кожен тестовий випадок починається рядком, що містить ціле число n (5n9) - розмір мінного поля n×n. Кожен з наступних n рядків містить по n символів Mij(1i, jn), Mij позначає поточний статус клітинки у рядку i та стовбці j, де '@' позначає міну, '0-8' позначають сумарні кількості мін в оточуючих клітинках, цифрою '0' позначені клітинки, по сусідству з якими мін немає. Гарантується, що всі положення коректні.

Вихідні дані

Для кожного тестового випадку у окремому рядку вивести повідомлення про номер тесту (починаючи з 1) і далі мінімальну кількість натиснень лівої кнопки миші (див. приклад вихідних даних).

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
1
9 
001@11@10
001111110
001111110
001@22@10
0012@2110
221222011
@@11@112@
2211111@2
000000111
Вихідні дані
Case 1: 24