우아한 다이아몬드

왕이 우아한 다이아몬드를 원해서 너를 고용했다. 우아한 다이아몬드는 숫자로 이루어진 2차원 도형이며, 가로축과 세로축 양쪽에 대해 대칭이다. 아래 네 도형은 모두 우아한 다이아몬드다.

   2
  3 3
 4 1 4
  3 3
   2

 8
8 8
 8

 3
2 2
 3

7

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

 2
1 1
 1

  1
 1 2
1 1 1
 2 1
  1

  3
 1 1
3 1 3
 1 1
  2

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

  1
 1 1

 2
222
 2

8   8
  0
00000

왕이 다이아몬드를 하나 준다. 이 다이아몬드는 우아하지 않을 수도 있다. 숫자를 덧붙여 더 큰 다이아몬드로 확장해서 우아하게 만들어야 한다. 돈을 많이 쓰고 싶지 않으므로 비용을 최소로 해야 한다.

정의

크기 $k$의 다이아몬드는 0부터 9까지의 숫자를 하나의 공백으로 구분해 적은 $2k-1$개의 줄이며, 다음과 같이 배치한다.

• $1 \le i \le k$인 줄 $i$는 공백 $k-i$개를 적은 뒤 숫자 $i$개를 하나의 공백으로 구분해 적는다.
• $k < i < 2k$인 줄 $i$는 공백 $i-k$개를 적은 뒤 숫자 $2k-i$개를 하나의 공백으로 구분해 적는다.

크기 $k$의 우아한 다이아몬드는 다음 두 대칭을 모두 만족하는 크기 $k$의 다이아몬드다.

• 가로 대칭: 줄 $i$의 숫자 개수를 $c_i$라 하자. 줄 $i$의 $j$번째 숫자($j=1$이 첫 숫자)는 줄 $i$의 $c_i+1-j$번째 숫자와 같다.
• 세로 대칭: 줄 $i$의 $j$번째 숫자($i=1$이 첫 줄)는 줄 $2k-i$의 $j$번째 숫자와 같다.

크기 $k$의 다이아몬드에 숫자를 덧붙이는 것을 확장이라 한다. 크기 $k$의 다이아몬드를 확장한 결과는 다음을 만족한다.

• 결과는 크기가 $k$ 이상인 다이아몬드다.
• 원래 다이아몬드가 결과 안에 그대로 들어 있다. 즉 어떤 $X$와 $Y$가 존재해서, 원래 다이아몬드의 줄 $i$의 $j$번째 문자가 (공백이 아니라) 숫자인 모든 $i$와 $j$에 대해 결과의 줄 $i+Y$의 $j+X$번째 문자도 숫자이고 그 숫자가 같다.

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

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 $k$가 홀로 적힌 한 줄과 그 뒤에 오는 크기 $k$의 다이아몬드로 이루어진다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 주어진 다이아몬드를 우아한 다이아몬드로 확장하는 최소 비용이다. 이미 우아한 다이아몬드라면 $y$는 0이다.

예제에는 네 개의 케이스가 있다. 앞의 두 케이스는 이미 우아한 다이아몬드이므로 비용이 0이다.

세 번째 다이아몬드는 다음과 같이 확장할 수 있다.

  3
 1 1
1 2 1
 1 1
  3

가능한 확장이 여럿 있지만 이 확장의 비용 5가 가장 작다.

네 번째 다이아몬드는 다음과 같이 확장할 수 있고, 비용은 7이다.

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