등차 정사각형

정수로 이루어진 $3 \times 3$ 격자가 주어진다. 격자의 $i$번째 행과 $j$번째 열에 있는 정수를 $\mathbf{G_{i,j}}$라고 하자. 여기서 $i$와 $j$는 $0$부터 인덱싱된다. 격자 중앙의 정수 $G_{1,1}$는 빠져 있다. 이 정사각형의 행, 열, 대각선 중 등차수열을 이루는 것의 최대 개수를 구한다. 빠진 수는 어떤 정수로든 대체할 수 있다.

등차수열은 연속한 항 사이의 차이가 일정한 수열이다. 수학적으로는 이를 $a_n = a_{n-1} + d$로 나타낼 수 있으며, 여기서 $d$는 공차이다. 이 문제에서 하나의 수열은 행, 열 또는 대각선 중 하나에 있는 $3$개의 수가 될 수 있다. 빠진 값을 정수로 대체하여, 그 결과로 얻은 수열들의 집합에서 찾을 수 있는 등차수열의 개수를 최대화해야 한다.

두 수열이 서로 다른 행, 열 또는 대각선에서 나온 경우 서로 다른 수열로 간주한다. 예를 들어 가운데 행을 가로지르는 수열 $\{2, 4, 6\}$와 맨 위 행을 가로지르는 수열 $\{2, 4, 6\}$는 두 수열로 세지만, 같은 행, 열 또는 대각선을 가로지르는 수열 $\{2, 4, 6\}$와 $\{6, 4, 2\}$는 하나의 수열로 센다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i, j$에 대해 $\mathbf{G_{i,j}}$는 정수이다.

테스트 세트 1

시간 제한: 20초. 모든 $i, j$에 대해 $|\mathbf{G_{i,j}}| \le 50$.

테스트 세트 2

시간 제한: 40초. 모든 $i, j$에 대해 $|\mathbf{G_{i,j}}| \le 10^9$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 3개의 줄로 이루어진다. 각 테스트 케이스의 첫 번째 줄에는 3개의 정수 $\mathbf{G_{0,0}}$, $\mathbf{G_{0,1}}$, $\mathbf{G_{0,2}}$가 주어진다. 각 테스트 케이스의 두 번째 줄에는 2개의 정수 $\mathbf{G_{1,0}}$와 $\mathbf{G_{1,2}}$가 주어진다. 각 테스트 케이스의 마지막 줄에는 3개의 정수 $\mathbf{G_{2,0}}$, $\mathbf{G_{2,1}}$, $\mathbf{G_{2,2}}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, $y$는 빠진 원소를 정한 뒤 격자의 행, 열, 대각선으로 만들 수 있는 등차수열의 가능한 최대 개수이다.

예제 케이스 #1에서 빠진 수를 $5$로 정하면 정확히 $4$개의 등차수열이 있다.

• 왼쪽 위 대각선: $[3, 5, 7]$

• 오른쪽 위 대각선: $[-1, 5, 11]$

• 가운데 열: $[4, 5, 6]$

• 오른쪽 열: $[11, 9, 7]$

빠진 수를 다른 어떤 정수로 정해도 수열은 $1$개뿐이다. 따라서 답은 $4$이다.

예제 케이스 #2에서 빠진 수를 $4$로 정하면 정확히 $3$개의 등차수열이 있다.

• 오른쪽 위 대각선: $[6, 4, 2]$

• 가운데 행: $[3, 4, 5]$

• 왼쪽 열: $[4, 3, 2]$

빠진 수를 다른 어떤 정수로 정하면 등차수열의 개수가 더 적어지므로 $3$를 출력한다.

예제 케이스 #3에서 빠진 수를 $9$로 정하면 가능한 모든 등차수열을 얻는다. 등차수열은 총 $8$개이며 각각은 $[9, 9, 9]$이므로 $8$를 출력한다.