#213518. [GCJ 2010 #2] Elegant Diamond

The king has hired you to make him an elegant diamond. An elegant diamond is a two-dimensional object made out of digits that's symmetric about a horizontal and a vertical axis. For example, the following four shapes are elegant diamonds:

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

These three shapes are diamonds, but are not elegant:

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

These three shapes are not diamonds:

  1     2     8   8
 1 1   222      0
        2     00000

The king will start by giving you a diamond, which may not be elegant. Your job is to make it elegant by enhancing it, adding digits on to make a bigger diamond. Because you don't want to spend too much money, you want to do it with as little cost as possible.

Definitions

A diamond of size is lines of digits, 0-9, separated by single spaces, organized in the following way:

• Line () contains spaces, then digits separated by single spaces.
• Line () contains spaces, then digits separated by single spaces.

An elegant diamond of size is a diamond of size with the following two symmetry properties:

• Horizontal symmetry: Let be the number of digits on line . The digit on line (where for the first digit) must be the same as the digit.
• Vertical symmetry: The digit on line (where for the first line) must be the same as the digit on line .

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

• The result is a diamond of size .
• The original diamond is part of the result. In other words, there exist some and some such that, for all values of and such that the character of the line of the original is a digit (as opposed to a space), the character on the line of the result is also a digit and it's the same as the character on the line of the original.

The cost of enhancing a diamond is equal to 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, . test cases follow. Each test case consists of a single integer in a line on its own, followed by a diamond of size .

For each test case, output one line containing "Case #: ", where is the case number (starting from 1) and is the minimum cost required to enhance the given diamond into an elegant diamond. If the diamond is already elegant, .

样例输入 1

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

样例输出 1

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

Sample Explanation

There are four cases. The first two cases start as elegant diamonds of size 1 and 2, respectively, and don't need to be enhanced; so the cost is 0. The third case can be enhanced to look like:

  3
 1 1
1 2 1
 1 1
  3

There are several possible enhancements, but this is one with the lowest possible cost, which is 5. In the fourth case we can enhance the diamond into the following elegant diamond:

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

...for a cost of 7.

Limits

Small dataset (4 Pts, Test set 1 - Visible)

• Time limit: 30 3 seconds.

Large dataset (8 Pts, Test set 2 - Hidden)

• Time limit: 60 6 seconds.