Коридор Каїр

Пентагональна плитка Каїра являє собою розбиття площини за допомогою напівправильних п'ятикутників. Ця плитка отримала свою назву, оскільки деякі вулиці в Каїрі вимощені з використанням такого дизайну.

Розглянемо кінцеву укладку, де кожен п'ятикутник може бути або порожнім (білим), або заповненим (сірим). Коридор - це максимальний набір порожніх суміжних п'ятикутників, які з'єднують чотири межі плитки. П'ятикутники вважаються суміжними, якщо вони мають спільну сторону, а не лише кут. Легко переконатися, що в кожній укладці може бути не більше одного коридору. Коридор вважається мінімальним, якщо в ньому немає зайвих п'ятикутників, тобто якщо будь-який п'ятикутник коридору заповнити, то решта п'ятикутників вже не утворюватиме коридор.

На рисунку вище показані чотири приклади укладки плитки. У перших трьох випадках є коридор, виділений жовтим кольором. Коридори (а) і (б) є мінімальними, але на рисунку (с) це не так: наприклад, плитки, позначені символом Х, можуть бути заповнені, і коридор все ще існуватиме. У крайньому правому прикладі коридору немає. Рисунки (а) і (с) відповідають першому прикладу.

Напишіть програму, яка зчитує текстові описи укладки плитки і для кожного з них визначає, чи існує коридор і чи є він мінімальним. У разі існування мінімального коридору програма повинна обчислити його розмір, тобто кількість порожніх пентагональних плит у коридорі.

Вхідні дані

Перша стрічка містить кількість укладок $t$ (1 \leq t \leq 10). Перша стрічка кожної укладки містить два натуральних числа n_k і m_k (1 \leq n_1 + n_2 + \ldots + n_t \leq 250 - загальне число рядків, 1 \leq m_1 + m_2 + \ldots + m_t \leq 250 - загальне число пар плиток). Кожен з наступних n_k рядків містить 2 \cdot m_k цифр, що описують пари a_{ij}, b_{ij} плит ($0$ - порожньо і $1$ - заповнено) в чергуючому горизонтальному / вертикальному порядку за шаблоном "шахової дошки", як показано на рисунку нижче.