16063 | 우아한 다이아몬드

왕은 자신을 위해 우아한 다이아몬드를 만들도록 당신을 고용했다. 우아한 다이아몬드는 숫자로 만들어진 이차원 물체로, 가로축과 세로축에 대해 대칭이다. 예를 들어, 다음 네 도형은 우아한 다이아몬드이다.

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

다음 세 도형은 다이아몬드이지만 우아하지는 않다.

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

다음 세 도형은 다이아몬드가 아니다.

1     2     8   8
 1 1   222      0
        2     00000

왕은 먼저 우아하지 않을 수도 있는 다이아몬드를 하나 줄 것이다. 당신의 임무는 숫자를 추가해 더 큰 다이아몬드로 확장하여 이를 우아하게 만드는 것이다. 비용을 너무 많이 쓰고 싶지 않으므로, 가능한 한 적은 비용으로 이 작업을 수행하려 한다.

크기가 k인 다이아몬드는 숫자로 이루어진 2k-1개의 줄로, 0-9, 숫자들은 한 칸의 공백으로 구분되며 다음과 같이 배치된다.

크기가 k인 우아한 다이아몬드는 다음 두 가지 대칭 성질을 갖는 크기 k의 다이아몬드이다.

가로 대칭: $c_{i}$ 를 i번째 줄에 있는 숫자의 개수라고 하자. i번째 줄의 $j^{th}$ 번째 숫자(첫 숫자에 대해 j=1)는 $c_{i}$ +1- $j^{th}$ 번째 숫자와 같아야 한다.
세로 대칭: i번째 줄의 $j^{th}$ 번째 숫자(첫 줄에 대해 i=1)는 2k-i번째 줄의 $j^{th}$ 번째 숫자와 같아야 한다.

크기가 k인 다이아몬드는 숫자를 추가하여 확장할 수 있다. 크기가 k인 다이아몬드를 확장한 결과는 다음 성질을 갖는다.

결과는 크기가 ≥ k인 다이아몬드이다.
원래 다이아몬드는 결과의 일부이다. 다시 말해, 원본의 $i^{th}$ 번째 줄의 $j^{th}$ 번째 문자가 공백이 아니라 숫자인 모든 i와 j의 값에 대해, 결과의 i+ $Y^{th}$ 번째 줄에 있는 j+ $X^{th}$ 번째 문자도 숫자이며 원본의 $i^{th}$ 번째 줄에 있는 $j^{th}$ 번째 문자와 같도록 하는 어떤 X와 어떤 Y가 존재한다.

다이아몬드를 확장하는 비용은 확장 결과에 있는 숫자의 개수에서 원래 다이아몬드에 있는 숫자의 개수를 뺀 값과 같다.

메모리 제한: 1GB. 1 ≤ T ≤ 100.

시간 제한: 30초. 1 ≤ k ≤ 10.

시간 제한: 60초. 1 ≤ k ≤ 51.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄에 단독으로 주어지는 하나의 정수 k와 그 뒤에 주어지는 크기 k의 다이아몬드로 이루어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 주어진 다이아몬드를 우아한 다이아몬드로 확장하는 데 필요한 최소 비용이다. 다이아몬드가 이미 우아하다면, y=0.

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

네 가지 케이스가 있다. 처음 두 케이스는 각각 크기가 1와 2인 우아한 다이아몬드로 시작하며 확장할 필요가 없으므로, 비용은 0이다. 세 번째 케이스는 다음과 같은 모습으로 확장할 수 있다.

가능한 확장은 여러 가지이지만, 이는 가능한 최소 비용인 5이 드는 확장 중 하나이다. 네 번째 케이스에서는 다이아몬드를 다음의 우아한 다이아몬드로 확장할 수 있다.

...비용은 7이다.

우아한 다이아몬드