Arithmetic Square

You are given a 3×3 grid of integers. Let $G_{i,j}$ denote the integer in the i-th row and j-th column of the grid, where i and j are 0-indexed. The integer in the middle of the grid, $G_{1,1}$, is missing. Find the maximum number of rows, columns, and diagonals of this square that form arithmetic progressions. You can replace the missing number with any integer.

An arithmetic progression is a sequence of numbers such that the difference between consecutive terms is constant. In mathematical terms, this can be represented as $a_n = a_{n-1} + d$, where $d$ is the common difference. In this problem, a sequence can be the 3 numbers in a row, column, or diagonal. We replace the missing value by an integer that maximizes the number of arithmetic progressions among the resulting sequences.

Two sequences are considered different if they are from different rows, columns, or diagonals. For example, the sequence {2,4,6} across the middle row and {2,4,6} across the top row are counted as two sequences, but the sequences {2,4,6} and {6,4,2} across the same row, column, or diagonal are counted as one sequence.

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case consists of 3 lines.

The first line of each test case contains 3 integers, $G_{0,0}$, $G_{0,1}$, and $G_{0,2}$.

The second line of each test case contains 2 integers, $G_{1,0}$ and $G_{1,2}$.

The last line of each test case contains 3 integers, $G_{2,0}$, $G_{2,1}$, and $G_{2,2}$.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum possible number of arithmetic progressions that can be generated by the rows, columns, and diagonals of the grid after setting the missing element.

• $1 \le T \le 100$.
• $G_{i,j}$ are integers, for all i, j.

In Sample Case #1, if we set the missing number to be 5, we have exactly 4 arithmetic progressions.

• top left diagonal: [3,5,7]
• top right diagonal: [-1,5,11]
• middle column: [4,5,6]
• right column: [11,9,7]

If we set the missing number to any other integer, there would be only 1 progression. Thus, the answer is 4.

In Sample Case #2, if we set the missing number to be 4, we have exactly 3 arithmetic progressions.

• top right diagonal: [6,4,2]
• middle row: [3,4,5]
• left column: [4,3,2]

Setting the missing number to any other integer results in fewer progressions, so we output 3.

In Sample Case #3, if we set the missing number to be 9, we have all possible arithmetic progressions. There are 8 total progressions (each one is [9,9,9]), so we output 8.