Državno natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) / 2. dan natjecanja - 3. zadatak

Pod okriljem noći je nepoznat broj zatvorenika pobjegao iz obližnjeg zatvora.

Zatvorsko dvorište se sastoji od travnatih polja kvadratnog oblika organiziranih u n redaka i m stupaca.

Retci su označeni brojevima od 1 do n odozgo prema dolje, a stupci brojevima od 1 do m slijeva na desno.

Iz zatvorske zgrade se ulazi na dvorište u gornjem-lijevom kutu, a u donjem-desnom kutu dvorišta je pronađena rupa u ogradi kroz koju su zatvorenici umakli.

Dodatno, istraga je pokazala da je svaki zatvorenik bježao tako da je ušao iz zgrade na polje (1, 1) dvorišta te se kretao prema rupi u ogradi tako da se u svakom koraku pomaknuo na susjedno polje na desno ili na susjedno polje prema dolje.

Nakon točno n + m − 1 koraka zatvorenik je došao do polja (n, m) i pobjegao iz zatvora.

Na svakom polju kroz koje je prošao neki zatvorenik je ostao trag u travi.

Kako bi procijenili ozbiljnost incidenta, najprije je potrebno na temelju tragova odrediti koliko je najmanje moguće zatvorenika pobjeglo iz zatvora.

Zadano je k scenarija, a u svakom scenariju su poznata sva polja dvorišta na kojima postoji trag.

Za svaki scenarij, odredite najmanji mogući broj zatvorenika potreban da načini sve pronađene tragove.

Možete pretpostaviti da u svakom scenariju rješenje postoji odnosno da su svi tragovi nastali upravo na gore opisani način.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj k (1 ≤ k ≤ 5), broj scenarija. Slijedi k blokova gdje svaki blok opisuje jedan scenarij.

U prvom redu bloka nalaze se prirodni brojevi n i m (2 ≤ n, m ≤ 1500) – dimenzije dvorišta.

U svakom od sljedećih n redova nalazi se niz od točno m znakova koji predstavlja jedan redak dvorišta.

Polje na kojem postoji trag je označeno velikim slovom “X”, a polje na kojem nema traga znakom “.” (točka).

Izlazni podaci

Ispišite k redova. U j-ti red ispišite traženi najmanji mogući broj zatvorenika u j-tom scenariju.

Primjeri test​ podataka

Ulaz

1
6 6
XXX...
X.X...
XXXXX.
..X.XX
..XX.X
..XXXX

Izlaz

3

Ulaz

2
3 7
XXXXXX.
.X...X.
.XXXXXX
3 8
XXXXXXX.
XXX.X.XX
.XXXXXXX

Izlaz

2
4

Ulaz

1
4 7
XXXXXX.
X.XX.XX
XX.X.XX
XXXXXXX

Izlaz

5