Коридор Каїр
Пентагональна плитка Каїра являє собою розбиття площини за допомогою напівправильних п'ятикутників. Ця плитка отримала свою назву, оскільки деякі вулиці в Каїрі вимощені з використанням такого дизайну.
Розглянемо кінцеву укладку, де кожен п'ятикутник може бути або порожнім (білим), або заповненим (сірим). Коридор - це максимальний набір порожніх суміжних п'ятикутників, які з'єднують чотири межі плитки. П'ятикутники вважаються суміжними, якщо вони мають спільну сторону, а не лише кут. Легко переконатися, що в кожній укладці може бути не більше одного коридору. Коридор вважається мінімальним, якщо в ньому немає зайвих п'ятикутників, тобто якщо будь-який п'ятикутник коридору заповнити, то решта п'ятикутників вже не утворюватиме коридор.
На рисунку вище показані чотири приклади укладки плитки. У перших трьох випадках є коридор, виділений жовтим кольором. Коридори (а) і (б) є мінімальними, але на рисунку (с) це не так: наприклад, плитки, позначені символом Х, можуть бути заповнені, і коридор все ще існуватиме. У крайньому правому прикладі коридору немає. Рисунки (а) і (с) відповідають першому прикладу.
Напишіть програму, яка зчитує текстові описи укладки плитки і для кожного з них визначає, чи існує коридор і чи є він мінімальним. У разі існування мінімального коридору програма повинна обчислити його розмір, тобто кількість порожніх пентагональних плит у коридорі.
Вхідні дані
Перша стрічка містить кількість укладок t (1 ≤ t ≤ 10). Перша стрічка кожної укладки містить два натуральних числа n[k] і m[k] (1 ≤ n[1] + n[2] + ... + n[t] ≤ 250 - загальне число рядків, 1 ≤ m[1] + m[2] + ... + m[t] ≤ 250 - загальне число пар плиток). Кожен з наступних n[k] рядків містить 2 * m[k] цифр, що описують пари a[ij], b[ij] плит (0 - порожньо і 1 - заповнено) в чергуючому горизонтальному / вертикальному порядку за шаблоном "шахової дошки", як показано на рисунку нижче.
Вихідні дані
Виведіть t рядків; k-ий рядок повинен містити розмір коридору k-ої укладки, якщо мінімальний коридор існує, і NO MINIMAL CORRIDOR інакше.