Ліва кнопка миші
Мінер є досить популярною грою в операційній системі Windows. Мета гри полягає у пошуку мін і маркуванні їх положення. Ви розміщуєте клацанням правої кнопки миші невеличкий прапорець у клітинці, в якій на Вашу думку розміщена міна. Клацанням лівої кнопки миші можна відкрити клітинку, у якій на Вашу думку міни немає. Якщо у цьому квадраті все ж таки розміщена міна, то вона взривається і Ви програєте. У протилежному випадку є два варіанти. У першому випадку відкривається число від 1 до 8, яке показує сумарну кількість мін, що оточують дану клітинку. Наприклад, якщо Ви натиснули ліву кнопку миші і в квадраті висвітилось число 8, то це означає, що дана клітинка ооточена 8 клітинками з мінами, тобто всі 8 сусідніх клітинок містять міни. У другому випадку, якщо навколо цієї клітинки немає сусідніх мін, то крім цієї клітинки відкриваються і всі сусідні. Якщо в деяких з сусідніх клітинок також немає оточуючих мін, то процес відкриття сусідніх клітинок продовжується. Тобто фактично комп'ютер допомагає Вам відкрити всі вільні від мін сусідні клітинки. Мета гри полягає у відкритті всіх вільних від мін клітинок. Том дуже захоплюється цією грою, але, на жаль, його права кнопка миші пошкоджена і він може користуватись лише лівою кнопкою миші. Для того щоб уникгути можливого подальшоего пошкодження миші він хоче завершити гру натиснувши на ліву кнопку миші мінімальну кількість разів. Знаючи початкове положення у грі Вам необхідно визначити цю саму мінімальну кількість натиснень лівою кнопкою миші.
Вхідні дані
Перший рядок містить ціле число, яке вказує кількість тестових випадків T (T ≤ 12). Кожен тестовий випадок починається рядком, що містить ціле число n (5 ≤ n ≤ 9) - розмір мінного поля n×n. Кожен з наступних n рядків містить по n символів M_{ij }(1 ≤ i, j ≤ n), M_ij позначає поточний статус клітинки у рядку i та стовбці j, де '@' позначає міну, '0-8' позначають сумарні кількості мін в оточуючих клітинках, цифрою '0' позначені клітинки, по сусідству з якими мін немає. Гарантується, що всі положення коректні.
Вихідні дані
Для кожного тестового випадку у окремому рядку вивести повідомлення про номер тесту (починаючи з 1) і далі мінімальну кількість натиснень лівої кнопки миші (див. приклад вихідних даних).