Binary Matris 2

Sizə r×c ölçüsündə bir matrisa verilir. Bu matrisanın hər bir elementi ya 0, ya da 1 ola bilər. Hər bir əməliyyatda matrisanın istənilən elementini dəyişə bilərsiniz, yəni 0ı 1ə və ya 1i 0a çevirə bilərsiniz. Məqsədiniz matrisanı elə dəyişdirməkdir ki:

1. Hər bir sırada eyni sayda 1 olsun və

2. Hər bir sütunda eyni sayda 1 olsun.

Bu məqsədə çatmaq üçün lazım olan minimum əməliyyat sayını tapın.

Giriş verilənləri

Giriş müsbət tam ədəd T ( 1000) ilə başlayır ki, bu da test hallarının sayını göstərir.

Hər bir hal iki tam ədəd m və n (1 ≤ r, c ≤ 40) ilə başlayır, burada r matrisanın sıra sayını, c isə sütun sayını göstərir. Sonra gələn m sətirdə hər biri n tam ədəd olacaq, ya 0, ya da 1.

Çıxış verilənləri

Hər bir test halı üçün "Case #: R" formatında bir sətir çıxarın, burada # hal nömrəsi ilə əvəz olunacaq və R hədəf matrisanı əldə etmək üçün lazım olan minimum addım sayını göstərəcək. Əgər hədəf matrisaya çatmaq mümkün deyilsə, R yerinə -1 yazın.

Nümunələr