== include(page="template/taskheader" task_id="boundingbox") ==

Poveste şi cerinţă...

Se dă o matrice binară $A$ cu $R$ linii şi $C$ coloane. Dacă alegem aleator, cu probabilitate uniformă, o submulţime (posibil vidă) de celule numerotate cu *1*, ce arie va avea în medie submatricea de arie minimă care conţine toate celulele selectate?

h2. Date de intrare

Fişierul de intrare $boundingbox.in$ ...

Fişierul de intrare $boundingbox.in$ va conţine pe prima sa linie numărul de teste $T$. Fiecare test va respecta următorul format: Prima linie conţine cele două numere, $R$ şi $C$, iar următoarele $R$ linii conţin câte $C$ caractere, constituind matricea $A$.

h2. Date de ieşire

În fişierul de ieşire $boundingbox.out$ ...

În fişierul de ieşire $boundingbox.out$ se vor afla $T$ linii, fiecare conţinând răspunsul pentru testul corespunzător. Răspunsul va respecta formatul "X/Y", unde $X$ şi $Y$ sunt numere naturale prime între ele. Cu alte cuvinte, răspunsul *trebuie să ia forma unei fracţii ireductibile*.

h2. Restricţii
* $1 ≤ T ≤ 1000$
* $1 ≤ R * C ≤ 50$

* Pentru $20%$ din teste, numărul celulelor de tip *1* din fiecare matrice este cel mult $12$
* Pentru alte $40%$ din teste are loc relaţia $T ≤ 100$

h2. Exemplu
table(example). |_. boundingbox.in |_. boundingbox.out |

| 1

| 2

2 3
101
010

1 1
0

| 5/2

0/1

|
== include(page="template/taskfooter" task_id="boundingbox") ==

10209