Cổng

Cho một lưới hình chữ nhật $A$ kích thước $n\times m$ gồm $n$ hàng và $m$ cột. Mỗi ô của lưới hoặc là ô đá (ký hiệu $1$) hoặc là ô trống (ký hiệu $0$). Trong một thao tác, bạn có thể đổi một ô đá thành ô trống hoặc một ô trống thành ô đá.

Một hình chữ nhật con $M$ kích thước $a\times b$ (gồm $a$ hàng và $b$ cột) được gọi là một cổng nếu thoả mãn đồng thời các điều kiện sau:

• $a\ge 5$ và $b\ge 4$.
• Với mọi $1<x<a$: ô $M_{x,1}$ và ô $M_{x,b}$ là ô đá (hai cột biên trái/phải, trừ hai đầu).
• Với mọi $1<x<b$: ô $M_{1,x}$ và ô $M_{a,x}$ là ô đá (hai hàng biên trên/dưới, trừ hai đầu).
• Với mọi $1<x<a$ và $1<y<b$: ô $M_{x,y}$ là ô trống (toàn bộ phần bên trong).
• Bốn ô góc $M_{1,1}$, $M_{1,b}$, $M_{a,1}$, $M_{a,b}$ có thể là loại bất kỳ.

Nói cách khác: viền của cổng (trừ bốn góc) phải toàn là đá, phần lõi bên trong phải toàn là trống, còn bốn góc thì tuỳ ý. Lưu ý thứ tự kích thước: phải có đúng $a$ hàng và $b$ cột, không phải $b$ hàng và $a$ cột.

Hãy tìm số thao tác ít nhất cần thực hiện trên lưới $A$ để tồn tại ít nhất một hình chữ nhật con là một cổng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa hai số nguyên $n$ và $m$.
  • $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự $0$ hoặc $1$ mô tả lưới: ký tự thứ $j$ của dòng thứ $i$ là $0$ nếu ô $A_{i,j}$ trống, là $1$ nếu ô $A_{i,j}$ là đá.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số thao tác ít nhất để lưới có ít nhất một hình chữ nhật con là cổng.

Ràng buộc

• $t\ge 1$.
• $5\le n\le 400$, $4\le m\le 400$.
• Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $400$.
• Tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $400$.

Ví dụ