등차 정사각형

3×3 정수 격자가 주어진다. 격자의 i번째 행 j번째 열에 있는 정수를 $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}는 한 개로 센다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다.

각 테스트 케이스는 3줄로 이루어진다.

각 테스트 케이스의 첫 줄에는 3개의 정수 $G_{0,0}$, $G_{0,1}$, $G_{0,2}$가 주어진다.

둘째 줄에는 2개의 정수 $G_{1,0}$, $G_{1,2}$가 주어진다.

마지막 줄에는 3개의 정수 $G_{2,0}$, $G_{2,1}$, $G_{2,2}$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 비어 있는 원소를 채운 뒤 격자의 행, 열, 대각선으로 만들 수 있는 등차수열 개수의 최댓값이다.

• $1 \le T \le 100$.
• 모든 i, j에 대해 $G_{i,j}$는 정수이다.

예제 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을 출력한다.