Untitled

Với bản tính hay trêu chọc của mình Dế Choắt đã bị chị cốc nhốt vào trong một khối đất hình lập phương có kích thước NxNxN cm ( 5<= N <= 30),

 

có một mặt tiếp giáp với mặt đất và 5 mặt khác không tiếp giáp với vật khác.

 

Để thoát ra khỏi khối đất đó, Dế Choắt cần phải đào đất về phía 1 trong 5 mặt kia, tuy nhiên với thể trạng ốm yếu của mình Dế Choắt không thể đào được quá nhiều đất,

 

vì vậy Dế Choắt cần tìm một cách đào để thoát ra khỏi khối đất đó sao cho số lượng đất phải đào là ít nhất.




Cho thông tin về khối đất mà Dế Choắt bị nhốt, hãy tìm số lượng cm khối đất ít nhất mà Dế choắt cần phải đào để thoát khỏi khối đất đó.




Time limit: 3 second (Java : 6 sec).




[Input]




Dòng đầu tiên là số lượng test case T (T <= 50).




Mỗi test case bắt đầu bằng số N là kích thước của khối đất hình hộp chữ nhật.




Tiếp theo là N lát cắt liên tiếp của hình hộp lập phương, mỗi lát cắt được tách nhau bởi một dòng.




Lưu ý: Mỗi lát cắt được cắt từ trên xuống dưới tới phần tiếp xúc với mặt đất có kích thước NxNx1, được biểu thị dưới dạng một ma trận nhị phân vuông kích thước NxN,

 

giá trị 2 biểu thị vị trí Dế Choắt bị nhốt, 1 biểu thị vùng đó là đất, phần tử 0 biểu thị vùng đó rỗng. Ví dụ dưới đây là một lát cắt của hình hộp lập phương kích thước 5x5x5.




1 1 1 1 1   <- tầng trên cùng




1 1 1 0 1




0 1 0 0 1




1 1 1 1 1




1 1 1 1 1 <- tầng tiếp giáp với mặt đất




[Output]
In mỗi test case trên một dòng, bắt đầu là "#x", với x là số thứ tự của test case, tiếp là một dấu cách và số lượng cm khối đất ít nhất mà Dế Choắt cần đào để thoát khỏi khối đất đó.




[Sample]




Input
1




5

1 1 1 1 1

1 1 1 0 1

0 1 0 0 1

1 1 1 1 1

1 1 1 1 1

 

1 1 1 1 0

1 0 1 1 0

1 1 1 1 1

1 1 1 1 1

1 1 1 0 1

 

1 1 1 1 1

1 1 0 1 1

1 1 2 1 0

1 1 1 1 1

1 1 1 1 1

 

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

 

0 1 1 1 1

1 1 0 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1