Танд 0-1 гэсэн квадрат матриц өгөгдөв. Түүн дотор хэдэн квадрат байна вэ? Квадрат өргөн нь 1-тэй тэнцүү хатуу хүрээтэй дөрвөлжин байна. Квадрат дор хаяж $2 × 2$ хэмжээтэй байна. Бид зөвхөн хоёр төрлийн квадратад анхаарал хандуулж байна.

1. Бүх тал нь матрицын талтай парралель байх квадрат

2. Бүх тал нь матрицын талтай диагональ байх квадрат

Жишээ нь доор өгөгдсөн матрицуудаас 1-р төрөлд багтах цорын ганц квадрат байна.

0000000 

0111100 

0100100 

0100100 

0111100

Төрлөөсөө үл хамааран квадрат нь дор хаяж нэг $1$ агуулах ёстой ба өнцгөөрөө болон аль нэг талаараа өөр нэг $1$ -т хүрэх боломжгүй байна. Мэдээж хэрэг квадтаруудын талуудын урт ижил байх ёстой.

Тэгвэл энэхүү матрицад хэдэн дөрвөлжин байн вэ?

Оролт

Эхний мөр $t$ ($1 ≤ t ≤ 10000$) гэсэн бүхэл тоо агуулж байгаа ба $t$ нь оролтод хийгдсэн сорилын тохиолдлуудын тоо юм. Бүх тохиолдол нь $n$ and $m$ ($2 ≤ n, m ≤ 250$) гэсэн бүхэл тоо агуулсан мөрөөр эхлэх ба энэ үед $n$ нь эгнээний тоо бол $m$ нь баганы тоо юм. Доорх $n$ мөрнүүд нь тус бүрдээ (0$ or 1$) бүхий $m$ тэмдэгтүүдийг агуулж байна. Бүх сорилын тохиолдлуудад орсон тэмдэгтүүдийн нийлбэр тоо нь аливаа оролтод $10^{6}$ -аас хэтрэхгүй байна.

Гаралт

$i$ дахь мөрөн дахь $i$ дахь сорилын тохиолдын хариутай $t$ гэсэн мөрүүдийг гарга.