Gcj2009

Round 2

A. Crazy Rows

Source: [1]

คุณได้รับเมตริกซ์ขนาด N x N ที่มีค่า 0 กับ 1 คุณสามารถสลับสองแถวที่ติดกันในเมตริกซ์ได้

เป้าหมายของคุณคือการสลับให้ค่า 1 ทั้งหมดอยู่บนหรือล่างแนวทแยงมุมหลัก นั่นคือ สำหรับ X ที่ 1 <= X <= N, จะต้องไม่มี 1 ในแถวที่ X ที่อยู่ด้านขวาของคอลัมน์ X

ให้โปรแกรมพิมพ์จำนวนครั้งของการสลับที่น้อยที่สุดที่ต้องใช้

Input

• บรรทัดแรกระบุจำนวนเต็ม T, จากนั้นจะมีข้อมูลทดสอบ T ชุดหลังจากนั้น
• บรรทัดแรกของแต่ละชุดข้อมูลทดสอบระบุจำนวนเต็ม N จากนั้นอีก N บรรทัด ในแต่ละบรรทัดจะมีอักขระ N ตัว ซึ่งมีค่าเป็น 0 หรือ 1

Output

สำหรับแต่ละข้อมูลทดสอบ พิมพ์

Case #X: K

เมื่อ X แทนหมายเลขข้อมูลทดสอบ และ K เป็นจำนวนครั้งที่ต้องสลับที่น้อยที่สุด

รับประกันว่ามีคำตอบในทุก ๆ ข้อมูลทดสอบ