Winmine.exe#3088

Winmine.exe

10 секунд

64 мегабайти

Дуже складна

Windows Minesweeper (WinMine) — це одна з найвідоміших ігор у системі Windows. Правила досить прості, а партію можна зіграти лише за кілька хвилин. Спочатку коротко познайомимося з цією грою (якщо ви вже знайомі з нею, можете пропустити наступний абзац): Мета гри — відкрити всі клітинки, що не містять мін (натискаючи лівою кнопкою миші), і не натрапити на міну. Розташування мін визначається логікою. Клацання по ігровому полю відкриває те, що приховано під вибраною клітинкою або групою прилеглих клітинок (якщо вони суміжні, то одночасно може відкритися багато порожніх клітинок). Деякі клітинки порожні, інші містять числа від 1 до 8 — це кількість мін, прилеглих до відкритої клітинки. Гра виграється, коли всі порожні клітинки відкрито й жодна міна не вибухнула; усі решта мін, що залишилися, автоматично позначаються прапорцями комп'ютером. Особливістю "Сапера" є елемент випадковості на початкових та деяких проміжних етапах.

Вікіпедія

Джедді любить грати у WinMine у вільний час, бо ця гра проста і геніальна. Проте інколи його дратує, коли він потрапляє у невизначені ситуації під час гри. Розгляньмо, наприклад, наступну позицію:

У червоному колі на цьому малюнку дві залишкові клітинки абсолютно невизначені, і очевидно, що існує два можливих варіанти розташування ОДНІЄЇ міни, що залишилася. Коли Джедді стикається з такою проблемою, йому доводиться лише вгадувати. Іноді існує лише два можливих варіанти (як у прикладі), а іноді — і більше. Тому йому потрібен помічник, який би порахував кількість різних можливих розташувань мін за поточного стану ігрового поля.

Такий помічник був би дуже корисний і цікавий для Джедді, тому він негайно береться за програмування. На жаль, Джедді витратив увесь час на парах з програмування та алгоритмів, граючи у WinMine, а не вивчаючи матеріал, тому це складне завдання здається йому неможливим. Оскільки Джедді так любить WinMine, він просить допомоги у тебе — відмінного програміста. Щоб спростити задачу, він додав три обмеження:

Гарантується, що вказаний стан гри завжди міг виникнути лише після ОДНОГО клацання на початковій дошці.
У цьому стані, якщо дві невідкриті клітинки з'єднані безпосередньо або через інші невідкриті клітинки, то вони також двозв'язні. Тобто навіть після вилучення будь-якої іншої невідкритої клітинки ці дві залишаться з'єднаними. Тут клітинки вважаються з'єднаними лише якщо мають спільну сторону. Тобто, максимум чотири суміжні сусіди у кожної клітинки.
У цьому стані, якщо два числа з'єднані спільною стороною безпосередньо або через інші числа, усі невідкриті клітинки, що межують із цим з'єднаним набором чисел, також повинні бути з'єднані.

Допоможи Джедді, будь ласка!

Вхідні дані

Задається кілька тестових випадків. Перший рядок містить одне ціле число $T$ ( $1 \leq T \leq 50$ 1 \leq T \leq 50) — кількість тестів. Далі йдуть $T$ випадків. Для кожного випадку перший рядок містить три додатні числа $n$ , $m$ та $M$ ( $1 \leq n, m \leq 100$ 1 \leq n, m \leq 100, $1 \leq M \leq 1000$ 1 \leq M \leq 1000), де $n$ і $m$ — кількість рядків і стовпців ігрової дошки, а $M$ — загальна кількість мін на полі. Далі описується матриця $n \times m$ n \times m символів, що відображає поточний стан дошки. У цій матриці два типи символів:

Цифри від $0$ до $8$ : означає кількість мін навколо цієї клітинки (' $0$ ' означає порожню клітинку).
'.' (лапки для ясності): означає, що клітинка невідкрита.

Вихідні дані

Для кожного тесту виведіть одне ціле число з префіксом, що позначає номер тесту — кількість можливих розміщень мін у заданому стані, по модулю $1000003$ . Дивіться приклад виводу для деталей.

Приклади

Приклад 1