Elegant Diamond (Small)

The king hired you to make him an elegant diamond. An elegant diamond is a two dimensional figure made of digits that is symmetric about a horizontal axis and about a vertical axis. Each of the following four figures is an elegant diamond.

  2
 3 3
4 1 4
 3 3
  2

 8
8 8
 8

 3
2 2
 3

7

The next three figures are diamonds, but none of them is elegant.

 2
1 1
 1

  1
 1 2
1 1 1
 2 1
  1

  3
 1 1
3 1 3
 1 1
  2

The next three figures are not diamonds at all.

  1
 1 1

 2
222
 2

8   8
  0
00000

The king gives you one diamond, which may not be elegant. Your job is to make it elegant by enhancing it, that is, by adding digits so that it becomes a bigger diamond. You do not want to spend much, so you have to do it at the smallest possible cost.

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$ that has both of the following symmetry properties. Let $c_i$ be the number of digits on line $i$.

• Horizontal symmetry: the $j$th digit on line $i$ (where $j=1$ is the first digit) equals the $(c_i+1-j)$th digit on the same line.
• 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$ is 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. In other words, there exist integers $X$ and $Y$ such that, for every $i$ and $j$ where the $j$th character of the $i$th line of the original is a digit rather than a space, the $(j+X)$th character of the $(i+Y)$th line of the result is also a digit and holds the same value.

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

The first line of the input has the number of test cases, $T$. $T$ test cases follow. Each test case is 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 10$

For each test case, print one line in the form Case #x: y, where $x$ is the 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 has four cases. The first two are already elegant diamonds, of size 1 and of size 2, so they need no enhancement and the cost is 0. The third one can be enhanced into this diamond:

  3
 1 1
1 2 1
 1 1
  3

Several enhancements are possible, and this one reaches the lowest cost, 5. The fourth one can be enhanced into this diamond:

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

That costs 7.