Nhà vua đã thuê bạn tạo ra một viên kim cương thanh lịch. Một viên kim cương thanh lịch là một đối tượng hai chiều được tạo thành từ các chữ số, đối xứng qua cả trục ngang và trục dọc. Ví dụ, bốn hình sau đây là các viên kim cương thanh lịch:

   2       8      3     7
  3 3     8 8    2 2
 4 1 4     8      3
  3 3 
   2

Ba hình dưới đây là các viên kim cương, nhưng không thanh lịch:

  2       1        3
 1 1     1 2      1 1
  1     1 1 1    3 1 3
         2 1      1 1
          1        2

Ba hình dưới đây không phải là hình kim cương:

  1     2     8   8
 1 1   222      0
        2     00000

Nhà vua sẽ bắt đầu bằng việc đưa cho bạn một viên kim cương, có thể chưa thanh lịch. Nhiệm vụ của bạn là làm cho nó trở nên thanh lịch bằng cách nâng cấp nó, thêm các chữ số để tạo thành một viên kim cương lớn hơn. Vì bạn không muốn tốn quá nhiều tiền, bạn muốn thực hiện việc này với chi phí thấp nhất có thể.

Định nghĩa

Một viên kim cương kích thước \(k\) gồm \(2k-1\) dòng chứa các chữ số từ \(0\) đến \(9\), cách nhau bởi các khoảng trắng đơn, được tổ chức như sau:

• Dòng \(i\) (\(1 \le i \le k\)) chứa \(k-i\) khoảng trắng, sau đó là \(i\) chữ số cách nhau bởi các khoảng trắng đơn.
• Dòng \(i\) (\(k < i < 2k\)) chứa \(i-k\) khoảng trắng, sau đó là \(2k-i\) chữ số cách nhau bởi các khoảng trắng đơn.

Một viên kim cương thanh lịch kích thước \(k\) là một viên kim cương kích thước \(k\) có hai tính chất đối xứng sau:

• Đối xứng ngang: Gọi \(c_i\) là số lượng chữ số trên dòng \(i\). Chữ số thứ \(j\) trên dòng \(i\) (với \(j=1\) cho chữ số đầu tiên) phải giống với chữ số thứ \(c_i+1-j\).
• Đối xứng dọc: Chữ số thứ \(j\) trên dòng \(i\) (với \(i=1\) cho dòng đầu tiên) phải giống với chữ số thứ \(j\) trên dòng \(2k-i\).

Một viên kim cương kích thước \(k\) có thể được nâng cấp bằng cách thêm các chữ số vào đó. Kết quả của việc nâng cấp một viên kim cương kích thước \(k\) có các tính chất sau:

• Kết quả là một viên kim cương kích thước \(\ge k\).
• Viên kim cương ban đầu là một phần của kết quả. Nói cách khác, tồn tại một số \(X\) và một số \(Y\) sao cho, với mọi giá trị \(i\) và \(j\) mà ký tự thứ \(j\) của dòng thứ \(i\) của viên kim cương gốc là một chữ số (thay vì khoảng trắng), thì ký tự thứ \(j+X\) trên dòng thứ \(i+Y\) của kết quả cũng là một chữ số và nó giống với chữ số thứ \(j\) trên dòng thứ \(i\) của bản gốc.

Chi phí của việc nâng cấp một viên kim cương bằng số lượng chữ số trong viên kim cương kết quả trừ đi số lượng chữ số trong viên kim cương ban đầu.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, T. T bộ test tiếp theo. Mỗi bộ test gồm một số nguyên k trên một dòng riêng biệt, theo sau là một viên kim cương kích thước k.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là chi phí tối thiểu cần thiết để nâng cấp viên kim cương đã cho thành một viên kim cương thanh lịch. Nếu viên kim cương đã thanh lịch, y=0.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).

Phân nhóm

• Small dataset (Test set 1): \(1 \le \mathbf{k} \le 10\).
• Large dataset (Test set 2): \(1 \le \mathbf{k} \le 51\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
1
0
2
 1
2 2
 1
2
 1
1 2
 1
3
  1
 6 3
9 5 5
 6 3
  1

Case #1: 0
Case #2: 0
Case #3: 5
Case #4: 7

  3
 1 1
1 2 1
 1 1
  3

   9
  1 1
 6 3 6
9 5 5 9
 6 3 6
  1 1
   9

Nguồn

Google Code Jam 2010, Vòng 2, bài Elegant Diamond.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.