# Cairo Corridor

The *Cairo pentagonal tiling* is a decomposition of
the plane using semiregular pentagons. Its name is given
because several streets in Cairo are paved using variations of
this design.

Consider a bounded tiling where each pentagon is either
*clear* (white) or *filled in* (grey). A
*corridor* is a maximal set of clear adjacent pentagons
that connect the four borders of the tiling. Pentagons are
considered adjacent if they share an edge, not just a corner.
It is easy to verify that there can be at most one corridor in
each tiling. A corridor is said to be *minimal* if it
has no superfluous pentagon, that is, if any pentagon of the
corridor was filled in, the set of remaining pentagons would
not be a corridor.

(a) Minimal corridor |
(b) Minimal corridor |
(c) No minimal corridor |
(d) No corridor |

The figure above depicts four example tilings. In the first three cases, there is a corridor which is highlighted in yellow. Besides, the corridors of figures (a) and (b) are minimal, but the one in figure (c) is not: for example, the tiles marked ‘X’ (among others) could be filled in and a corridor would still exist. In the rightmost tiling there is no corridor.

The tilings shown in figures (a) and (c) correspond to sample input 1.

## Task

Write a program that reads textual descriptions of Cairo
tilings, and for each one determines if a corridor exists and
is minimal. In the latter case, the program should compute the
*size of the corridor*, i.e., the number of clear
pentagonal tiles of the corridor.

## Input

The first line of input is a positive decimal integer
$T$ of tilings to be
processed. Each tiling description $k$ has a first line with two positive
decimal integers, $N_ k$
and $M_ k$, separated by a
space. The following $N_
k$ lines contain $2 \cdot
M_ k$ binary digits representing pairs $a_{ij}, b_{ij}$ of tiles (`0` is clear and `1` is
full) in alternating horizontal/vertical adjacency following a
“checkerboard” pattern, as is illustrated in the figure
below.

## Constraints

$1$ |
$\leq $ |
$T$ |
$\leq $ |
$10$ |
Number of tilings |

$1$ |
$\leq $ |
$\sum _{k=1}^ T N_ k$ |
$\leq $ |
$250$ |
Total number of lines |

$1$ |
$\leq $ |
$\sum _{k=1}^ T M_ k$ |
$\leq $ |
$250$ |
Total number of tile pairs |

## Output

The output consists of $T$ lines; the $k$-th line should be the size of the
corridor of the $k$-th
tiling, if there exists a minimal corridor, and `NO MINIMAL CORRIDOR`, otherwise.

Sample Input 1 | Sample Output 1 |
---|---|

2 6 6 010101001001 001000101100 110101001101 010010000100 001110110010 001001101010 6 6 010010110010 001100100111 000110100101 011001100101 100100011100 011010001101 |
17 NO MINIMAL CORRIDOR |

Sample Input 2 | Sample Output 2 |
---|---|

1 3 4 11110111 01000000 11110111 |
9 |