Elegant Diamond

The king wants an elegant diamond and has hired you to make one. An elegant diamond is a two dimensional figure built from digits that is symmetric about a horizontal axis and about a vertical axis. Each of these four figures is an elegant diamond.

   2
  3 3
 4 1 4
  3 3
   2

 8
8 8
 8

 3
2 2
 3

7

Each of these three figures is a diamond, but it is not elegant.

 2
1 1
 1

  1
 1 2
1 1 1
 2 1
  1

  3
 1 1
3 1 3
 1 1
  2

None of these three figures is a diamond.

  1
 1 1

 2
222
 2

8   8
  0
00000

The king gives you a diamond that may not be elegant. You make it elegant by enhancing it: you add digits so that it grows into a bigger diamond. You do not want to spend much, so the cost has to be as small as possible.

Definitions

A diamond of size $k$ is $2k-1$ lines of digits from 0 to 9, separated by single spaces, laid out this way:

• Line $i$ with $1 \le i \le k$ has $k-i$ spaces, then $i$ digits separated by single spaces.
• Line $i$ with $k < i < 2k$ has $i-k$ spaces, then $2k-i$ digits separated by single spaces.

An elegant diamond of size $k$ is a diamond of size $k$ with both of these symmetry properties:

• Horizontal symmetry: let $c_i$ be the number of digits on line $i$. The $j$-th digit on line $i$ (where $j=1$ is the first digit) equals the $(c_i+1-j)$-th digit on line $i$.
• Vertical symmetry: the $j$-th digit on line $i$ (where $i=1$ is the first line) equals the $j$-th digit on line $2k-i$.

A diamond of size $k$ can be enhanced by adding digits to it. The result of enhancing a diamond of size $k$ has these properties:

• The result is a diamond of size at least $k$.
• The original diamond is part of the result. That is, there are values $X$ and $Y$ such that for every $i$ and $j$ where the $j$-th character of line $i$ of the original is a digit (not a space), the $(j+X)$-th character of line $i+Y$ of the result is also a digit and it is the same digit.

The cost of enhancing a diamond is the number of digits in the result of the enhancement minus the number of digits in the original diamond.

The first line of the input gives the number of test cases $T$. $T$ test cases follow. Each test case consists of a single integer $k$ on a line of its own, followed by a diamond of size $k$.

Limits

• $1 \le T \le 100$
• $1 \le k \le 51$

For each test case, print one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum cost of enhancing the given diamond into an elegant diamond. If the diamond is already elegant, $y$ is 0.

The sample holds four cases. The diamonds of the first two cases are already elegant, so the cost is 0.

The third diamond can be enhanced into

  3
 1 1
1 2 1
 1 1
  3

Several enhancements are possible, and this one has the lowest cost, 5.

The fourth diamond can be enhanced into

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

for a cost of 7.