Kair Dəhlizi

Пentaqonal plitka Qahir düzbucaqlı beşbucaqlardan istifadə edərək müstəvini bölən bir dizayndır. Bu ad, Qahirədə bir neçə küçənin bu dizaynla döşənməsi səbəbindən verilmişdir.

Son döşəməni nəzərdən keçirək, burada hər bir beşbucaq ya boş (ağ), ya da dolu (boz) olur. Koridor - plitkanın dörd sərhədini birləşdirən maksimum boş bitişik beşbucaqlar dəstidir. Beşbucaqlar, yalnız bir künc deyil, ümumi bir tərəfi varsa bitişik sayılır. Hər bir döşəmədə bir koridordan çox olmaması asandır. Koridor minimal sayılır, əgər onun artıq beşbucağı yoxdursa, yəni koridorun hər hansı bir beşbucağı doldurulsa, qalan beşbucaqlar dəsti artıq koridor olmayacaq.

Yuxarıdakı şəkildə dörd plitka döşəmə nümunəsi göstərilmişdir. İlk üç halda sarı rənglə vurğulanan bir koridor var. Bundan əlavə, (a) və (b) koridorları minimaldır, lakin (c) şəklində deyil: məsələn, X simvolu ilə işarələnmiş plitkalar doldurula bilər və koridor hələ də mövcud olacaq. Ən sağdakı döşəmədə koridor yoxdur. (a) və (c) şəkilləri birinci nümunəyə uyğundur.

Plitka döşəməsinin mətn təsvirlərini oxuyan və hər biri üçün koridorun olub-olmadığını və minimal olub-olmadığını müəyyən edən bir proqram yazın. Sonuncu halda, proqram koridorun ölçüsünü, yəni koridorda olan boş beşbucaqlı plitələrin sayını hesablamaq lazımdır.

Giriş məlumatları

İlk sətir döşəmələrin sayını t (1 ≤ t ≤ 10) ehtiva edir. Hər bir döşəmənin ilk sətri iki təbii ədəd n[k] və m[k] (1 ≤ n[1] + n[2] + ... + n[t] ≤ 250 - ümumi sıra sayı, 1 ≤ m[1] + m[2] + ... + m[t] ≤ 250 - ümumi plitə cütləri sayı) ehtiva edir. Növbəti n[k] sətirin hər biri 2 * m[k] rəqəmlərini ehtiva edir və a[ij], b[ij] plitə cütlərini təsvir edir (0 - boş və 1 - dolu) "şahmat taxtası" şablonunda göstərildiyi kimi üfüqi / şaquli ardıcıllıqla.

Çıxış məlumatları

t sətir çıxarın; k-cı sətir minimal koridor varsa, k-cı döşəmənin koridor ölçüsünü ehtiva etməlidir, əks halda NO MINIMAL CORRIDOR yazılmalıdır.