Problem Description

You are given a $3 \times 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 sequences which are arithmetic progressions. You can replace the missing number with any integer.

An arithmetic progression (also known as arithmetic sequence) 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 either a row, column or diagonal. We are looking to replace the missing value by an integer that maximizes the number of arithmetic progressions that can be found in the resulting set of 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 will be counted as $2$ sequences but the sequences $\{2, 4, 6\}$ and $\{6, 4, 2\}$ across the same row, column, or diagonal will be counted as one sequence.

Input Format

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}$.

Output Format

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.

3
3 4 11
10 9
-1 6 7
4 1 6
3 5
2 5 6
9 9 9
9 9
9 9 9

Case #1: 4
Case #2: 3
Case #3: 8

Hint

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$.

Limits

$1 \le T \le 100$.

$G_{i,j}$ are integers, for all $i, j$.

Test Set $1$

$|G_{i,j}| \le 50$, for all $i, j$.

Test Set $2$

$|G_{i,j}| \le 10^9$, for all $i, j$.